Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import re
class Tokens():
def __init__(self, s):
self.tokens = tokenize(s)
self.current_i = 0
def peek(self):
return self.tokens[self.current_i]
def consume(self):
t = self.tokens[self.current_i]
self.current_i += 1
return t
def tokenize(s):
"""
>>> tokenize("(1.1 + 2 * 3)")
['(', '1.1', '+', '2', '*', '3', ')']
"""
return re.findall("[0123456789.]+|[*+/\-()]", s)
"""
Exp E -> T | T+E | T-E
Term T -> P | P*T | P/T
Phrase P -> number | (E) | -number | -(E)
1 + 2 * 3 + 1
"""
def expression(tokens):
"""
>>> expression(['1'])
('1', [])
>>> expression(['1', '*', '2'])
(['*', '1', '2'], [])
>>> expression(['1', '+', '2'])
(['+', '1', '2'], [])
>>> expression(tokenize('1+2*3'))
(['+', '1', ['*', '2', '3']], [])
"""
t, rest_of_tokens = term(tokens)
if len(rest_of_tokens) == 0:
return t, rest_of_tokens
else:
token = rest_of_tokens[0]
if token in ['-', '+']:
rest_of_tokens.pop(0)
exp, rest_of_tokens = expression(rest_of_tokens)
return [token, t, exp], rest_of_tokens
else:
return t, rest_of_tokens
def term(tokens):
"""Term T -> P | P*T | P/T
>>> term(['1.2', '*', '123'])
(['*', '1.2', '123'], [])
>>> term(['1.2'])
('1.2', [])
>>> term(['1', '+', '2'])
('1', ['+', '2'])
"""
phra, rest_of_tokens = phrase(tokens)
if len(rest_of_tokens) == 0:
return phra, rest_of_tokens
else:
token = rest_of_tokens[0]
if token in ['*', '/']:
rest_of_tokens.pop(0)
t, rest_of_tokens = term(rest_of_tokens)
return [token, phra, t], rest_of_tokens
else:
return phra, rest_of_tokens
def is_numeric(s):
"""
>>> is_numeric('1')
True
"""
return all(l in '1234567890.' for l in s)
def phrase(tokens):
"""
>>> phrase(['1'])
('1', [])
>>> phrase(['1.213'])
('1.213', [])
>>> phrase(tokenize('(1)'))
('1', [])
"""
t = tokens.pop(0)
if is_numeric(t):
return t, tokens
elif t == '(':
e, rest_of_tokens = expression(tokens)
t = rest_of_tokens.pop(0)
if t != ')':
raise SyntaxError('whoops')
return e, rest_of_tokens
else:
assert False, 'uh oh, t was actually %r' % t
def gen_python_code(tree):
ops = {'+':'__import__("operator").add',
'-':'__import__("operator").sub',
'*':'__import__("operator").mul',
'/':'__import__("operator").div'}
if isinstance(tree, list):
operator, operand1, operand2 = tree
return 'reduce(%s, [%s, %s])' % (ops[operator], gen_python_code(operand1), gen_python_code(operand2))
else:
return tree
def gen_short_python_code(tree):
if isinstance(tree, list):
operator, operand1, operand2 = tree
return '(%s %s %s)' % (gen_short_python_code(operand1), operator, gen_short_python_code(operand2))
else:
return tree
if __name__ == '__main__':
import doctest
doctest.testmod()
print expression(tokenize('1+4*3-(2*4-3+(1+1))*8'))
s = gen_python_code(expression(tokenize('1+4*3-(2*4-3+(1+1))*8'))[0])
print s
print eval(s)
s = gen_short_python_code(expression(tokenize('1+4*3-(2*4-3+(1+1))*8'))[0])
print s
print eval(s)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment