import copy
import re
class Success(object):
def __init__(self, val, rest):
self.val = val
self.rest = rest
def __str__(self):
return 'Success(' + repr(self.val) + ', ' + repr(self.rest) + ')'
class Failure(object):
def __init__(self, rest):
self.rest = rest
def __str__(self):
return 'Failure(' + repr(self.rest) + ')'
class Trampoline(object):
def __init__(self):
self.stack = []
self.table = {}
def hasNext(self):
return self.stack != []
def step(self):
if self.hasNext():
(fn, argList) = self.stack.pop()
fn(*argList)
def pushCall(self, fn, *argList):
self.stack.append((fn, argList))
def push(self, fn, string, cont):
def tableRef(fn, string):
if fn in self.table:
fnMemo = self.table[fn]
if string not in fnMemo:
fnMemo[string] = ([], {})
return fnMemo[string]
else:
entry = ([], {})
fnMemo = {string : entry}
self.table[fn] = fnMemo
return entry
entry = tableRef(fn, string)
if not entry[0] and not entry[1]:
entry[0].append(cont)
def myCont(result):
if str(result) not in entry[1]:
entry[1][str(result)] = result
tempList = copy.deepcopy(entry[0])
for c in tempList:
c(result)
self.pushCall(fn, string, self, myCont)
else:
entry[0].append(cont)
tempDict = copy.deepcopy(entry[1])
for sr, r in tempDict.iteritems():
cont(r)
def run(self):
while self.hasNext():
self.step()
allCaches = []
def memo(fn):
cache = {}
allCaches.append(cache)
def memo_wrapper(*args):
sargs = str(args)
if sargs not in cache:
cache[sargs] = fn(*args)
return cache[sargs]
return memo_wrapper
@memo
def succeed(val):
def f(string, tramp, cont):
cont(Success(val, string))
return f
@memo
def lit(match):
def f(string, tramp, cont):
length = min(len(string), len(match))
head = string[0:length]
tail = string[length:]
if head == match:
cont(Success(head, tail))
else:
cont(Failure(string))
return f
@memo
def reg(pattern):
def f(string, tramp, cont):
result = re.findall('^' + pattern, string)
if not result:
cont(Failure(string))
else:
result = result[0]
length = len(result)
head = string[0:length]
tail = string[length:]
cont(Success(head, tail))
return f
def bind(p, fn):
def f(string, tramp, cont):
def myCont(result):
if isinstance(result, Success):
fn(result.val)(result.rest, tramp, cont)
else:
cont(result)
tramp.push(p, string, myCont)
return f
@memo
def seq(plist):
def seq_(a, b):
def f1(x):
def f2(y):
return succeed(x + [y])
return bind(b, f2)
return bind(a, f1)
return reduce(seq_, plist, succeed([]))
@memo
def alt(plist):
def f(string, tramp, cont):
for p in plist:
tramp.push(p, string, cont)
return f
@memo
def rep1(p):
def f(string, tramp, cont):
tramp.push(seq([p, rep1(p)]), string, cont)
tramp.push(p, string, cont)
return f
@memo
def rep0(p):
def f(string, tramp, cont):
tramp.push(rep1(p), string, cont)
tramp.push(succeed([]), string, cont)
return f
@memo
def opt(p):
def f(string, tramp, cont):
tramp.push(p, string, cont)
tramp.puch(succeed([]), string, cont)
return f
@memo
def ws(p):
def f(string, tramp, cont):
tramp.push(seq([reg(r'[\s]*'), p, reg(r'[\s]*')]), string, cont)
return f
@memo
def red(p, fn):
def f(val):
if type(val) == type([]):
return succeed(fn(*val))
else:
return succeed(fn(val))
return bind(p, f)
def runParser(parser, string):
results = []
tramp = Trampoline()
for cache in allCaches:
cache.clear()
def myCont(result):
if isinstance(result, Success) and result.rest == '':
results.append(result)
tramp.push(parser, string, myCont)
tramp.run()
return results
# =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= #
expr = (lambda *_:
alt([ red( seq([expr, lit('+'), term]),
lambda x, _, y: x + y),
red( seq([expr, lit('-'), term]),
lambda x, _, y: x - y),
term]) (*_))
term = (lambda *_:
alt([ red( seq([term, lit('*'), factor]),
lambda x, _, y: x * y),
red( seq([term, lit('/'), factor]),
lambda x, _, y: x / y),
factor]) (*_))
factor = (lambda *_:
alt ([ red( seq([ws(lit('(')), expr, ws(lit(')'))]),
lambda _, e, __: e),
red( seq([ws(lit('-')), factor]),
lambda _, f: -f),
number]) (*_))
number = red( ws(reg(r'[-+]?(?:0|[1-9][0-9]*)(?:\.[0-9]+)?')),
lambda _, n, __: float(n))
results = runParser(expr, '0.1*( \r1 + 2 * 5 \t+ -(15\n- 10) - - - 2*-1/0.5)')
print '\n'.join([str(r) for r in results]), '\n', len(results), 'result(s)'
aW1wb3J0IGNvcHkKaW1wb3J0IHJlCgpjbGFzcyBTdWNjZXNzKG9iamVjdCk6CgogICAgZGVmIF9faW5pdF9fKHNlbGYsIHZhbCwgcmVzdCk6CiAgICAgICAgc2VsZi52YWwgID0gdmFsCiAgICAgICAgc2VsZi5yZXN0ID0gcmVzdAoKICAgIGRlZiBfX3N0cl9fKHNlbGYpOgogICAgICAgIHJldHVybiAnU3VjY2VzcygnICsgcmVwcihzZWxmLnZhbCkgKyAnLCAnICsgcmVwcihzZWxmLnJlc3QpICsgJyknCgpjbGFzcyBGYWlsdXJlKG9iamVjdCk6CgogICAgZGVmIF9faW5pdF9fKHNlbGYsIHJlc3QpOgogICAgICAgIHNlbGYucmVzdCA9IHJlc3QKCiAgICBkZWYgX19zdHJfXyhzZWxmKToKICAgICAgICByZXR1cm4gJ0ZhaWx1cmUoJyArIHJlcHIoc2VsZi5yZXN0KSArICcpJwoKY2xhc3MgVHJhbXBvbGluZShvYmplY3QpOgoKICAgIGRlZiBfX2luaXRfXyhzZWxmKToKICAgICAgICBzZWxmLnN0YWNrID0gW10KICAgICAgICBzZWxmLnRhYmxlID0ge30KCiAgICBkZWYgaGFzTmV4dChzZWxmKToKICAgICAgICByZXR1cm4gc2VsZi5zdGFjayAhPSBbXQoKICAgIGRlZiBzdGVwKHNlbGYpOgogICAgICAgIGlmIHNlbGYuaGFzTmV4dCgpOgogICAgICAgICAgICAoZm4sIGFyZ0xpc3QpID0gc2VsZi5zdGFjay5wb3AoKQogICAgICAgICAgICBmbigqYXJnTGlzdCkKCiAgICBkZWYgcHVzaENhbGwoc2VsZiwgZm4sICphcmdMaXN0KToKICAgICAgICBzZWxmLnN0YWNrLmFwcGVuZCgoZm4sIGFyZ0xpc3QpKQoKICAgIGRlZiBwdXNoKHNlbGYsIGZuLCBzdHJpbmcsIGNvbnQpOgoKICAgICAgICBkZWYgdGFibGVSZWYoZm4sIHN0cmluZyk6CiAgICAgICAgICAgIGlmIGZuIGluIHNlbGYudGFibGU6CiAgICAgICAgICAgICAgICBmbk1lbW8gPSBzZWxmLnRhYmxlW2ZuXQoKICAgICAgICAgICAgICAgIGlmIHN0cmluZyBub3QgaW4gZm5NZW1vOgogICAgICAgICAgICAgICAgICAgIGZuTWVtb1tzdHJpbmddID0gKFtdLCB7fSkKCiAgICAgICAgICAgICAgICByZXR1cm4gZm5NZW1vW3N0cmluZ10KICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIGVudHJ5ID0gKFtdLCB7fSkKICAgICAgICAgICAgICAgIGZuTWVtbyA9IHtzdHJpbmcgOiBlbnRyeX0KCiAgICAgICAgICAgICAgICBzZWxmLnRhYmxlW2ZuXSA9IGZuTWVtbwoKICAgICAgICAgICAgICAgIHJldHVybiBlbnRyeQoKICAgICAgICBlbnRyeSA9IHRhYmxlUmVmKGZuLCBzdHJpbmcpCgogICAgICAgIGlmIG5vdCBlbnRyeVswXSBhbmQgbm90IGVudHJ5WzFdOgogICAgICAgICAgICBlbnRyeVswXS5hcHBlbmQoY29udCkKCiAgICAgICAgICAgIGRlZiBteUNvbnQocmVzdWx0KToKICAgICAgICAgICAgICAgIGlmIHN0cihyZXN1bHQpIG5vdCBpbiBlbnRyeVsxXToKICAgICAgICAgICAgICAgICAgICBlbnRyeVsxXVtzdHIocmVzdWx0KV0gPSByZXN1bHQKCiAgICAgICAgICAgICAgICAgICAgdGVtcExpc3QgPSBjb3B5LmRlZXBjb3B5KGVudHJ5WzBdKQoKICAgICAgICAgICAgICAgICAgICBmb3IgYyBpbiB0ZW1wTGlzdDoKICAgICAgICAgICAgICAgICAgICAgICAgYyhyZXN1bHQpCgogICAgICAgICAgICBzZWxmLnB1c2hDYWxsKGZuLCBzdHJpbmcsIHNlbGYsIG15Q29udCkKICAgICAgICBlbHNlOgogICAgICAgICAgICBlbnRyeVswXS5hcHBlbmQoY29udCkKCiAgICAgICAgICAgIHRlbXBEaWN0ID0gY29weS5kZWVwY29weShlbnRyeVsxXSkKCiAgICAgICAgICAgIGZvciBzciwgciBpbiB0ZW1wRGljdC5pdGVyaXRlbXMoKToKICAgICAgICAgICAgICAgIGNvbnQocikKCiAgICBkZWYgcnVuKHNlbGYpOgogICAgICAgIHdoaWxlIHNlbGYuaGFzTmV4dCgpOgogICAgICAgICAgICBzZWxmLnN0ZXAoKQoKYWxsQ2FjaGVzID0gW10KCmRlZiBtZW1vKGZuKToKICAgIGNhY2hlID0ge30KICAgIGFsbENhY2hlcy5hcHBlbmQoY2FjaGUpCgogICAgZGVmIG1lbW9fd3JhcHBlcigqYXJncyk6CiAgICAgICAgc2FyZ3MgPSBzdHIoYXJncykKCiAgICAgICAgaWYgc2FyZ3Mgbm90IGluIGNhY2hlOgogICAgICAgICAgICBjYWNoZVtzYXJnc10gPSBmbigqYXJncykKICAgICAgICByZXR1cm4gY2FjaGVbc2FyZ3NdCgogICAgcmV0dXJuIG1lbW9fd3JhcHBlcgoKQG1lbW8KZGVmIHN1Y2NlZWQodmFsKToKCiAgICBkZWYgZihzdHJpbmcsIHRyYW1wLCBjb250KToKICAgICAgICBjb250KFN1Y2Nlc3ModmFsLCBzdHJpbmcpKQoKICAgIHJldHVybiBmCgpAbWVtbwpkZWYgbGl0KG1hdGNoKToKCiAgICBkZWYgZihzdHJpbmcsIHRyYW1wLCBjb250KToKICAgICAgICBsZW5ndGggPSBtaW4obGVuKHN0cmluZyksIGxlbihtYXRjaCkpCgogICAgICAgIGhlYWQgPSBzdHJpbmdbMDpsZW5ndGhdCiAgICAgICAgdGFpbCA9IHN0cmluZ1tsZW5ndGg6XQoKICAgICAgICBpZiBoZWFkID09IG1hdGNoOgogICAgICAgICAgICBjb250KFN1Y2Nlc3MoaGVhZCwgdGFpbCkpCiAgICAgICAgZWxzZToKICAgICAgICAgICAgY29udChGYWlsdXJlKHN0cmluZykpCgogICAgcmV0dXJuIGYKCkBtZW1vCmRlZiByZWcocGF0dGVybik6CgogICAgZGVmIGYoc3RyaW5nLCB0cmFtcCwgY29udCk6CiAgICAgICAgcmVzdWx0ID0gcmUuZmluZGFsbCgnXicgKyBwYXR0ZXJuLCBzdHJpbmcpCgogICAgICAgIGlmIG5vdCByZXN1bHQ6CiAgICAgICAgICAgIGNvbnQoRmFpbHVyZShzdHJpbmcpKQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIHJlc3VsdCA9IHJlc3VsdFswXQogICAgICAgICAgICBsZW5ndGggPSBsZW4ocmVzdWx0KQoKICAgICAgICAgICAgaGVhZCA9IHN0cmluZ1swOmxlbmd0aF0KICAgICAgICAgICAgdGFpbCA9IHN0cmluZ1tsZW5ndGg6XQoKICAgICAgICAgICAgY29udChTdWNjZXNzKGhlYWQsIHRhaWwpKQoKICAgIHJldHVybiBmCgpkZWYgYmluZChwLCBmbik6CgogICAgZGVmIGYoc3RyaW5nLCB0cmFtcCwgY29udCk6CgogICAgICAgIGRlZiBteUNvbnQocmVzdWx0KToKICAgICAgICAgICAgaWYgaXNpbnN0YW5jZShyZXN1bHQsIFN1Y2Nlc3MpOgogICAgICAgICAgICAgICAgZm4ocmVzdWx0LnZhbCkocmVzdWx0LnJlc3QsIHRyYW1wLCBjb250KQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgY29udChyZXN1bHQpCgogICAgICAgIHRyYW1wLnB1c2gocCwgc3RyaW5nLCBteUNvbnQpCgogICAgcmV0dXJuIGYKCkBtZW1vCmRlZiBzZXEocGxpc3QpOgoKICAgIGRlZiBzZXFfKGEsIGIpOgogICAgICAgIGRlZiBmMSh4KToKICAgICAgICAgICAgZGVmIGYyKHkpOgogICAgICAgICAgICAgICAgcmV0dXJuIHN1Y2NlZWQoeCArIFt5XSkKICAgICAgICAgICAgcmV0dXJuIGJpbmQoYiwgZjIpCiAgICAgICAgcmV0dXJuIGJpbmQoYSwgZjEpCgogICAgcmV0dXJuIHJlZHVjZShzZXFfLCBwbGlzdCwgc3VjY2VlZChbXSkpCgpAbWVtbwpkZWYgYWx0KHBsaXN0KToKCiAgICBkZWYgZihzdHJpbmcsIHRyYW1wLCBjb250KToKICAgICAgICBmb3IgcCBpbiBwbGlzdDoKICAgICAgICAgICAgdHJhbXAucHVzaChwLCBzdHJpbmcsIGNvbnQpCgogICAgcmV0dXJuIGYKCkBtZW1vCmRlZiByZXAxKHApOgoKICAgIGRlZiBmKHN0cmluZywgdHJhbXAsIGNvbnQpOgogICAgICAgIHRyYW1wLnB1c2goc2VxKFtwLCByZXAxKHApXSksIHN0cmluZywgY29udCkKICAgICAgICB0cmFtcC5wdXNoKHAsIHN0cmluZywgY29udCkKCiAgICByZXR1cm4gZgoKQG1lbW8KZGVmIHJlcDAocCk6CgogICAgZGVmIGYoc3RyaW5nLCB0cmFtcCwgY29udCk6CiAgICAgICAgdHJhbXAucHVzaChyZXAxKHApLCBzdHJpbmcsIGNvbnQpCiAgICAgICAgdHJhbXAucHVzaChzdWNjZWVkKFtdKSwgc3RyaW5nLCBjb250KQoKICAgIHJldHVybiBmCgpAbWVtbwpkZWYgb3B0KHApOgoKICAgIGRlZiBmKHN0cmluZywgdHJhbXAsIGNvbnQpOgogICAgICAgIHRyYW1wLnB1c2gocCwgc3RyaW5nLCBjb250KQogICAgICAgIHRyYW1wLnB1Y2goc3VjY2VlZChbXSksIHN0cmluZywgY29udCkKCiAgICByZXR1cm4gZgoKQG1lbW8KZGVmIHdzKHApOgoKICAgIGRlZiBmKHN0cmluZywgdHJhbXAsIGNvbnQpOgogICAgICAgIHRyYW1wLnB1c2goc2VxKFtyZWcocidbXHNdKicpLCBwLCByZWcocidbXHNdKicpXSksIHN0cmluZywgY29udCkKCiAgICByZXR1cm4gZgoKQG1lbW8KZGVmIHJlZChwLCBmbik6CgogICAgZGVmIGYodmFsKToKICAgICAgICBpZiB0eXBlKHZhbCkgPT0gdHlwZShbXSk6CiAgICAgICAgICAgIHJldHVybiBzdWNjZWVkKGZuKCp2YWwpKQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIHJldHVybiBzdWNjZWVkKGZuKHZhbCkpCgogICAgcmV0dXJuIGJpbmQocCwgZikKCmRlZiBydW5QYXJzZXIocGFyc2VyLCBzdHJpbmcpOgogICAgcmVzdWx0cyA9IFtdCiAgICB0cmFtcCA9IFRyYW1wb2xpbmUoKQoKICAgIGZvciBjYWNoZSBpbiBhbGxDYWNoZXM6CiAgICAgICAgY2FjaGUuY2xlYXIoKQoKICAgIGRlZiBteUNvbnQocmVzdWx0KToKICAgICAgICBpZiBpc2luc3RhbmNlKHJlc3VsdCwgU3VjY2VzcykgYW5kIHJlc3VsdC5yZXN0ID09ICcnOgogICAgICAgICAgICByZXN1bHRzLmFwcGVuZChyZXN1bHQpCgogICAgdHJhbXAucHVzaChwYXJzZXIsIHN0cmluZywgbXlDb250KQogICAgdHJhbXAucnVuKCkKCiAgICByZXR1cm4gcmVzdWx0cwoKIyA9LT0tPS09LT0tPS09LT0tPS09LT0tPS09LT0tPS09LT0tPS09LT0tPS09LT0tPS09LT0tPS09LT0tPS09LT0tPS09LT0tPS09LT0gIwoKZXhwciA9IChsYW1iZGEgKl86CiAgICBhbHQoWyByZWQoIHNlcShbZXhwciwgbGl0KCcrJyksIHRlcm1dKSwKICAgICAgICAgICAgICAgbGFtYmRhIHgsIF8sIHk6IHggKyB5KSwKICAgICAgICAgIHJlZCggc2VxKFtleHByLCBsaXQoJy0nKSwgdGVybV0pLAogICAgICAgICAgICAgICBsYW1iZGEgeCwgXywgeTogeCAtIHkpLAogICAgICAgICAgdGVybV0pICgqXykpCgp0ZXJtID0gKGxhbWJkYSAqXzoKICAgIGFsdChbIHJlZCggc2VxKFt0ZXJtLCBsaXQoJyonKSwgZmFjdG9yXSksCiAgICAgICAgICAgICAgIGxhbWJkYSB4LCBfLCB5OiB4ICogeSksCiAgICAgICAgICByZWQoIHNlcShbdGVybSwgbGl0KCcvJyksIGZhY3Rvcl0pLAogICAgICAgICAgICAgICBsYW1iZGEgeCwgXywgeTogeCAvIHkpLAogICAgICAgICAgZmFjdG9yXSkgKCpfKSkKCmZhY3RvciA9IChsYW1iZGEgKl86CiAgICBhbHQgKFsgcmVkKCBzZXEoW3dzKGxpdCgnKCcpKSwgZXhwciwgd3MobGl0KCcpJykpXSksCiAgICAgICAgICAgICAgICBsYW1iZGEgXywgZSwgX186IGUpLAogICAgICAgICAgIHJlZCggc2VxKFt3cyhsaXQoJy0nKSksIGZhY3Rvcl0pLAogICAgICAgICAgICAgICAgbGFtYmRhIF8sIGY6IC1mKSwKICAgICAgICAgICBudW1iZXJdKSAoKl8pKQoKbnVtYmVyID0gcmVkKCB3cyhyZWcocidbLStdPyg/OjB8WzEtOV1bMC05XSopKD86XC5bMC05XSspPycpKSwKICAgICAgICAgICAgICBsYW1iZGEgXywgbiwgX186IGZsb2F0KG4pKQoKcmVzdWx0cyA9IHJ1blBhcnNlcihleHByLCAnMC4xKiggXHIxICsgMiAgKiAgNSBcdCsgLSgxNVxuLSAxMCkgLSAtIC0gMiotMS8wLjUpJykKcHJpbnQgJ1xuJy5qb2luKFtzdHIocikgZm9yIHIgaW4gcmVzdWx0c10pLCAnXG4nLCBsZW4ocmVzdWx0cyksICdyZXN1bHQocykn