Created
March 7, 2014 07:20
-
-
Save globby/9406905 to your computer and use it in GitHub Desktop.
An infix evaluator implementing the shunting yard algorithm
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
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