Skip to content

Instantly share code, notes, and snippets.

@pstephens
Created December 26, 2017 18:11
Show Gist options
  • Save pstephens/93d537d6733959a9d881befdd511733d to your computer and use it in GitHub Desktop.
Save pstephens/93d537d6733959a9d881befdd511733d to your computer and use it in GitHub Desktop.
A simple expression evaluator in Python.
"""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