Script to evaluate mathematical expressions in infix notation.

evaluate_infix.py

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()))