Shunting Yard Algorithm in Python

The Shunting Yard Algorithm is a classic algorithm for parsing mathematical expressions invented by Edsger Dijkstra. Its name comes from the use of a stack to rearrange the operators and operands into the correct order for evaluation, which is rather reminiscent of a railway siding.

Here is a very simple implementation in Python:

def is_number(str):
try:
int(str)
return True
except ValueError:
return False

def is_name(str):
return re.match("\w+", str)

def peek(stack):
return stack[-1] if stack else None

def apply_operator(operators, values):
operator = operators.pop()
right = values.pop()
left = values.pop()
values.append(eval("{0}{1}{2}".format(left, operator, right)))

def greater_precedence(op1, op2):
precedences = {'+' : 0, '-' : 0, '*' : 1, '/' : 1}
return precedences[op1] > precedences[op2]

def evaluate(expression):
tokens = re.findall("[+/*()-]|\d+", expression)
values = []
operators = []
for token in tokens:
if is_number(token):
values.append(int(token))
elif token == '(':
operators.append(token)
elif token == ')':
top = peek(operators)
while top is not None and top != '(':
apply_operator(operators, values)
top = peek(operators)
operators.pop() # Discard the '('
else:
# Operator
top = peek(operators)
while top is not None and top not in "()" and greater_precedence(top, token):
apply_operator(operators, values)
top = peek(operators)
operators.append(token)
while peek(operators) is not None:
apply_operator(operators, values)

return values[0]


Example program:

def main():
expression = '((20 - 10 ) * (30 - 20) / 10 + 10 ) * 2'
print("Shunting Yard Algorithm: {0}".format(evaluate(expression)))
print("Python: {0}".format(eval(expression)))

if __name__ == '__main__':
main()


Output:

Shunting Yard Algorithm: 40
Python: 40