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.