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