Skip to content

Instantly share code, notes, and snippets.

@JackMorris JackMorris/evaluate_infix.py Secret
Created Apr 12, 2014

Embed
What would you like to do?
Script to evaluate mathematical expressions in infix notation.
def to_stack(input_string):
""" Converts an input string to a stack representation. For example, to_stack('123') = ['3', '2', '1']. """
return list(reversed(input_string.replace(' ', '')))
def pop_next_number(input_stack):
""" Takes a list of characters, popping the first number from the end of the list, returning None if no such value.
For example, pop_next_number(['*', '2', '1']) = 12, removing '1' and '2' from input list
pop_next_number(['1', '-']) = None
"""
output = ''
while len(input_stack) > 0 and input_stack[-1] in '1234567890':
output += input_stack.pop()
if len(output) == 0:
return None
return float(output)
def apply_operation(result_stack, op):
""" Applies op to the operands on the top of result_stack, pushing the result back on the stack. """
if len(result_stack) < 2:
raise ValueError('Incorrect infix formatting.')
operand2, operand1 = result_stack.pop(), result_stack.pop()
if op is '+':
result_stack.append(operand1 + operand2)
elif op is '-':
result_stack.append(operand1 - operand2)
elif op is '*':
result_stack.append(operand1 * operand2)
elif op is '/':
result_stack.append(operand1 / operand2)
elif op is '^':
result_stack.append(operand1 ** operand2)
else:
raise ValueError('Unknown operator ' + op + '.')
def has_higher_precedence(operation1, operation2):
""" Returns True if operation1 has higher precedence than operation 2.
For this purpose, brackets do not have a higher precedence than standard operators, as they are handled differently.
"""
precedence_map = {'^': 0, '*': 1, '/': 1, '+': 2, '-': 2}
if operation1 in precedence_map:
if operation2 in precedence_map:
return precedence_map[operation1] < precedence_map[operation2]
else:
return True
return False
def calculate(infix_string):
""" Calculates and returns the sum represented in infix notation by the input string.
For example, calculate('2 + 3 * (4 + 5)') = 29.
"""
infix_stack, operation_stack, result_stack = to_stack(infix_string), [], []
while len(infix_stack) > 0:
next_number = pop_next_number(infix_stack)
if next_number is not None:
# Next input is a number, so just shift to result stack.
result_stack.append(next_number)
else:
# Top of stack is an operator (or a bracket).
operation = infix_stack.pop()
if operation is '(':
operation_stack.append('(')
elif operation is ')':
# Perform all operations following matching '(', and then pop it.
while len(operation_stack) > 0 and operation_stack[-1] is not '(':
apply_operation(result_stack, operation_stack.pop())
if len(operation_stack) == 0:
raise ValueError('Incorrect infix formatting.')
operation_stack.pop()
else:
# Standard operation. Perform pending operations of higher precedence first.
while len(operation_stack) > 0 and has_higher_precedence(operation_stack[-1], operation):
apply_operation(result_stack, operation_stack.pop())
operation_stack.append(operation)
while len(operation_stack) > 0:
# Apply any other operations after input is consumed.
apply_operation(result_stack, operation_stack.pop())
if len(result_stack) != 1:
raise ValueError('Incorrect infix formatting.')
return result_stack[0]
if __name__ == '__main__':
print(calculate(input()))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.