Created
December 26, 2017 18:11
-
-
Save pstephens/93d537d6733959a9d881befdd511733d to your computer and use it in GitHub Desktop.
A simple expression evaluator in Python.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
"""Implements a simple expression evaluator. | |
Supported syntax: | |
1. Balanced parenthesis for grouping. | |
2. Numbers. Can include a decimal point. | |
3. Negation ('-' as a prefix unary operator) | |
4. Binary operators for '*', '/', '+', and '-'. | |
Order of operations follow typical rules: | |
1. Grouping. (1+2) | |
2. Negation. -(1+2) | |
3. Multiplication and division, left to right. 3*5/6 | |
4. Addition and subtraction, left to right. 3+5-6 | |
Multiple steps: | |
1. tokenize(s) - takes a string and turns into an iter of Token objects. | |
2. parse(line) - takes a string and turns into an AST rooted in a Node. Returns None if line can not be parsed. | |
3. calc(ast) - takes an AST and evaluates it. This largely delegates to Node's calc method. | |
""" | |
import re | |
import collections | |
class ParseError(Exception): | |
pass | |
class Token: | |
NUMBER = 0 | |
OPERATION = 1 | |
LPAREN = 2 | |
RPAREN = 3 | |
END = 4 | |
NAMES = {0: "NUMBER", | |
1: "OPERATION", | |
2: "LPAREN", | |
3: "RPAREN", | |
4: "END"} | |
def __init__(self, toktype, v): | |
self.toktype = toktype | |
self.v = v | |
def toktype_to_name(self): | |
return Token.NAMES.get(self.toktype, "UNKNOWN") | |
def __repr__(self): | |
return f"Token({self.toktype_to_name()}, {self.v!r})" | |
class Node: | |
def calc(self): raise NotImplementedError | |
class BinOp(Node): | |
def __init__(self, left, right): | |
self.left = left | |
self.right = right | |
def __repr__(self): | |
return f"{type(self).__name__}({self.left!r}, {self.right!r})" | |
def calc(self): | |
left = self.left.calc() | |
right = self.right.calc() | |
return self.calc_bin_op(left, right) | |
def calc_bin_op(self, left, right): raise NotImplementedError | |
class UnOp(Node): | |
def __init__(self, operand): | |
self.operand = operand | |
def __repr__(self): | |
return f"{type(self).__name__}({self.operand!r})" | |
def calc(self): | |
operand = self.operand.calc() | |
return self.calc_un_op(operand) | |
def calc_un_op(self, operand): raise NotImplementedError | |
class Number(Node): | |
def __init__(self, val): | |
self.val = val | |
def __repr__(self): | |
return f"Number({self.val!r})" | |
def calc(self): return self.val | |
def make_bin_op_class(name, f): | |
class Op(BinOp): | |
def calc_bin_op(self, left, right): return f(left, right) | |
Op.__name__ = name | |
return Op | |
def make_un_op_class(name, f): | |
class Op(UnOp): | |
def calc_un_op(self, operand): return f(operand) | |
Op.__name__ = name | |
return Op | |
AddOp = make_bin_op_class("AddOp", lambda l, r: l + r) | |
SubOp = make_bin_op_class("SubOp", lambda l, r: l - r) | |
MulOp = make_bin_op_class("MulOp", lambda l, r: l * r) | |
DivOp = make_bin_op_class("DivOp", lambda l, r: l / r) | |
NegOp = make_un_op_class("NegOp", lambda o: -o) | |
def tokenize(s: str): | |
patt = r"""([0-9]+(?:\.[0-9]*)?)|([-+*/])|(\()|(\))|(\s+)|(.)""" | |
for num, op, lparen, rparen, ws, other in re.findall(patt, s): | |
if num: | |
yield Token(Token.NUMBER, float(num)) | |
elif op: | |
yield Token(Token.OPERATION, op) | |
elif lparen: | |
yield Token(Token.LPAREN, lparen) | |
elif rparen: | |
yield Token(Token.RPAREN, rparen) | |
elif ws: | |
pass | |
else: | |
raise ParseError(f"Unexpected character '{other}'.") | |
yield Token(Token.END, None) | |
def parse(line): | |
def peek(): return tokens[0] | |
def pop(): return tokens.popleft() | |
def parse_add_sub(): | |
left = parse_mul_div() | |
while True: | |
tok = peek() | |
if tok.toktype == Token.OPERATION: | |
if tok.v == '+': | |
pop() | |
right = parse_mul_div() | |
left = AddOp(left, right) | |
elif tok.v == '-': | |
pop() | |
right = parse_mul_div() | |
left = SubOp(left, right) | |
else: | |
break | |
else: | |
break | |
return left | |
def parse_mul_div(): | |
left = parse_neg() | |
while True: | |
tok = peek() | |
if tok.toktype == Token.OPERATION: | |
if tok.v == '*': | |
pop() | |
right = parse_neg() | |
left = MulOp(left, right) | |
elif tok.v == '/': | |
pop() | |
right = parse_neg() | |
left = DivOp(left, right) | |
else: | |
break | |
else: | |
break | |
return left | |
def parse_neg(): | |
tok = peek() | |
if tok.toktype == Token.OPERATION and tok.v == '-': | |
pop() | |
return NegOp(parse_neg()) | |
else: | |
return parse_group() | |
def parse_group(): | |
tok = peek() | |
if tok.toktype == Token.LPAREN: | |
pop() | |
node = parse_add_sub() | |
tok = pop() | |
if tok.toktype != Token.RPAREN: | |
raise ParseError("Expected RPAREN.") | |
return node | |
else: | |
return parse_term() | |
def parse_term(): | |
tok = pop() | |
if tok.toktype != Token.NUMBER: | |
raise ParseError("Expected NUMBER.") | |
else: | |
return Number(tok.v) | |
try: | |
tokens = collections.deque(tokenize(line)) | |
expr = parse_add_sub() | |
last_tok = pop() | |
if last_tok.toktype != Token.END: | |
raise ParseError(f"Unexpected token at the end: {last_tok!r}.") | |
else: | |
return expr | |
except ParseError as p: | |
print(p) | |
return None | |
def calc(expr): | |
try: | |
return expr.calc() | |
except ZeroDivisionError: | |
print("Divide by zero.") | |
return None | |
def do_repl(): | |
while True: | |
try: | |
line = input("calc> ") | |
except KeyboardInterrupt: | |
print() | |
print("Bye!") | |
break | |
if not line: | |
continue | |
expr = parse(line) | |
result = expr and calc(expr) | |
if result is not None: | |
print(result) | |
if __name__ == "__main__": | |
do_repl() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment