Write an evaluator for mathematical expressions. Sample expressions:

3                       // = 3
1 + 2                   // = 3
1 + 2 + 3               // = 6
2 * 3 + 4               // = 10
2 + 3 * 4               // = 14
2 + 3 * 4 - 7 + 3 / 3   // = 8

Background

The notation, which looks most natural to us and is taught at schools is called infix. In infix operators are written in between of operands. The order of evaluation of operations can be left-to-right or right-to-left. It depends on the order of precedence of operators in expression.

There are two other equivalent notations, called postfix and prefix.

In postfix notation operators are written after operands. The order of evaluation is always the same: left-to-right. Unlike in infix, order of evaluation is fixed. There are no brackets, and no way to override the flow.

2 3 4 * + // equivalent of "2 + 3 * 4" in infix

In prefix notation operators are written before operands. As in postfix evaluation is always left-to-right and brackets cannot be used to override the flow.

+ 3 * 4 2 // also equivalent of "2 + 3 * 4" in infix

Sample algorithm

The simple way to evaluate infix expression is first to convert it to postfix and then evaluate postfix, which is more strict and easier to implement.

1. To convert infix to postfix have a stack for operators and read infix expression from left to right:
   1. If number: print it out.
   2. If operator: push to stack until the operator with lower precedence appears. When operator with lower precedence appears, then pop it from stack and print it.
2. To evaluate postfix have a stack for numbers and read postfix expression from left to right:
   1. If number: push to stack.
   2. If operator:
      1. Pop top two numbers off the stack (note that they are popped out in reverse order)
      2. Perform operation on those two numbers.
      3. Push resulting number to stack.

Sample implementation

My sample implementation is in PHP with PhpSpec. See github repository with full source code.

If you have other implementation - please share in comment.

This exercise is inspired by CS 61B: Data Structures lecture from Berkeley University.