Permalink
Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
43 lines (37 sloc) 1.3 KB
from collections import deque
def shunting_yard(expr, operators, left_par = '(', right_par = ')'):
'''Infix to postfix notation convertor using shunting-yard algorithm'''
precedence = dict([(op, i) for i, op in enumerate(operators)])
precedence[left_par] = -1
precedence[right_par] = -1
operators = set(operators)
output = deque()
stack = deque()
for token in expr:
if token in operators:
while stack and precedence[stack[-1]] > precedence[token]:
output.append(stack.pop())
stack.append(token)
elif token == left_par:
stack.append(token)
elif token == right_par:
while stack:
if stack[-1] != left_par:
output.append(stack.pop())
else:
stack.pop()
break
else:
raise ValueError('Unbalanced parentheses')
else:
output.append(token)
stack.reverse()
for operator in stack:
if operator == left_par:
raise ValueError('Unbalanced parentheses')
output.append(operator)
return list(output)
if __name__ == '__main__':
opers = ['or', 'and']
expr = ['(', 0, 'or', 1, ')', 'and', 2]
print shunting_yard(expr, opers)