Skip to content

Instantly share code, notes, and snippets.

@globby
Created March 7, 2014 07:20
Show Gist options
  • Save globby/9406905 to your computer and use it in GitHub Desktop.
Save globby/9406905 to your computer and use it in GitHub Desktop.
An infix evaluator implementing the shunting yard algorithm
import re
from operator import *
class Math(Exception):
pass
class InfixException(Math):
pass
re_float = re.compile(r'^(\d+\.\d*)|(\d*\.\d+)$')
re_int = re.compile(r'^\d+$')
class Infix:
def __init__(self):
self.op_map = {
'(':(15,None,None,None),
'~':(14,'R',inv,1),
'!':(14,'R',lambda x: 1 if x == 0 else 0,1),
'*':(13,'L',mul,2),
'/':(13,'L',div,2),
'%':(13,'L',mod,2),
'+':(12,'L',add,2),
'-':(12,'L',sub,2),
'&':(8,'L',and_,2),
'^':(7,'L',xor,2),
'|':(6,'L',or_,2),
')':(0,None,None,None)
}
self.numeric = "1234567890."
self.operators = "+-*/%^|!~()"
def bufout(self):
if self.buff:
if re_float.match(self.buff):
self.out.append(float(self.buff))
elif re_int.match(self.buff):
self.out.append(int(self.buff))
else:
raise InfixException("'%s' not of type 'int' or 'float'" % self.buff)
self.buff = ""
def get(self,key,token):
keys = ['prec','assoc','op','args']
return self.op_map[token][keys.index(key)]
def apply(self,token):
op, args = self.get('op',token), self.get('args',token)
if len(self.out) >= args:
self.out.append(op(*[self.out.pop() for i in range(args)][::-1]))
else:
raise InfixException("Not enough arguments to apply operation '%s'" % token)
def eval(self,expr):
self.out, self.stack = [], []
self.buff = ""
for token in expr:
if token in self.numeric:
self.buff += token
elif token in self.operators[:-4]:
self.bufout()
p = self.get('prec',token)
while self.stack and self.get('prec',self.stack[-1]) >= p and self.stack[-1] != '(':
self.apply(self.stack.pop())
self.stack.append(token)
elif token in self.operators[-4:-2]:
self.bufout()
p = self.get('prec',token)
while self.stack and self.get('prec',self.stack[-1]) > p and self.stack[-1] != '(':
self.apply(self.stack.pop())
self.stack.append(token)
elif token in self.operators[-2]:
self.bufout()
self.stack.append(token)
elif token in self.operators[-1]:
self.bufout()
while self.stack and self.stack[-1] != '(':
token = self.stack.pop()
self.apply(token)
if self.stack and self.stack[-1] == '(':
self.stack.pop()
self.bufout()
while self.stack:
token = self.stack.pop()
if token in self.operators[:-2]:
self.apply(token)
return self.out[0] if len(self.out) == 1 else self.out
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment