Convert a mathematical expression into RPN

This is a very common technique and actually it has been described in thousand of places. We are given a string representing a mathematical expression, and we are expected to convert it into Reverse Polish Notation what makes evaluation way easier. As an example let’s consider a following expression 2 + 5 * 4 that in a RPN has a form of 2 5 4 * +.

So we have an expression given in an infix notation and we need to convert it to RPN. Not to make the problem to difficult we assume there are no function operators, nor separators and neither unary minus. So basically we have only positive numbers, parenthesis and basic arithmetic operations like +, -, *, /. And what is the most important we assume the expression is correct, so no need to validate (even if it was pretty simple it’s not a part of the problem).

The conversion algorithm has been created by Dijkstra and is called Shunting-yard algorithm. The algorithm uses two data structures, a queue Q and a stack S:

while there are tokens to read
    t = the next token
    if isNumber(t) then Q.push(t)
    if isOperator(t) then
        while isOperator(S.top())
              and priority(S.top()) > priority(t) then
           Q.push(S.pop());
        S.push(t);
    if isLeftParenthesis(t) then
       S.push(t);
    if isRightParenthesis(t) then
       while ! isLeftParenthesis(S.top()) then
          Q.push(S.pop());
       Q.pop()
while S.empty() == false
    Q.push(S.pop());

An interesting part is in the line 6 of this code, where we are considering the order of operations. As we know the operations * and / have higher priority than + and – so they should be executed before. Then we are poping them from the stack and putting into the queue.

Best Regards

Joe Kidd