Convert infix notation to reverse polish notation (Java)

Tags: , , , ,

How to implement a calculator is a popular interview question. To answer this question well, you need to maser Stack data structures, convert an infix notation to RPN and evaluate reverse polish notation. 

Since the input is usually in infix notation, e.g. “3 + 6 * 2”, it is difficult develop a program to evaluate it directly.

In practice, we can implement a calculator algorithm into two steps:

  1. the first step is to convert your mathematical expressions, which is called infix notation, into Reverse Polish Notation (RPN), or postfix notation.  
  2. The second step to evaluate the RPN using a Stack based algorithm. 

What are Infix notation and Reverse polish Notation

Infix notation

Infix notation is the common arithmetic and logical formula notation, which are used by us every day. For example (2 + 6 * 4) / (3 + 8) is a typical infix notation. 

Although infix notation is natural for us, it is more difficult to parse by computers than prefix notation ( e.g. + 2 2 ) or postfix notation ( e.g. 2 2 + ).

Reverse polish Notation

Reverse polish Notation (RPN), also known as postfix notation, is mathematical notation in which every operator (eg. + – * %) follows all of its operands.

The benefits of RPN is that it does not need any parentheses as long as each operator has a fixed number of operands.

For the infix expression 5 - 2, the corresponding RPN is 5 2 -

The following table compares Infix notation and RPN using different examples:

Infix notation Reverse Polish Notation
A – B A B –
A ^ 2 + 3 * A * B + B ^ 4 A 2 ^ 3 A * B * + B 4 ^ +
( ( 1  + 3 ) / 4 ) ^ 5 1  3 + 4 / 5 ^
( 1 + 2 ) * ( 3 / 4 ) ^ ( a + b ) 1 2 + 3 4 / a b + ^ *

Convert Infix notation to RPN

The most famous algorithm to convert infix notation to RPN is the shunting-yard algorithm. The algorithm was invented by Edsger Dijkstra and named the “shunting yard” algorithm because its operation resembles that of a railroad shunting yard.

Similar to the evaluation of RPN,  the shunting yard algorithm is also stack based. We define two data variables:

  1. A queue Q to hold the final reverse polish notation.
  2. A stack S to hold the operators that not added to the output queue. 

In the convert process, we scan the tokens in the infix notation,

  1. If the current token is a number, we put it into the queue
  2. If the current token is an operator, we will do some rule check to determine when to put in to the stack. 

The rules are based on the operator precedence, and whether it is a left associative or right associate operator. 

Given an infix expression like "2 + 6 * ( 3 - 4)",  the resulted RPN is "2 6 3 4 - * +" . Once we get the RPN, we can easily develop a program to evaluate this postfix notation.

Pseudo code of the shunting-yard algorithm

Suppose we build a operator that only supports +, -, *, /, (, ), we can first define precedence for each of the operator as following. 

A simplified shunting-yard algorithm likes this:

Here are the import rules of the algorithm:

  • When read a number, it is immediately added to the output queue Q.
  • When read an '(', it is immediately added to the operator stack S
  • when read an ‘)‘, keep popping S until get ‘(‘, and add all the popped operators to Q
  • At the end of reading, pop all operators off the stack and put them into the Q
  • when read an operator, we need to check its precedence with the operator in the top of the stack. 

A simple explanation of the shunting-yard algorithm

We use a simple example to walk through the shunting-yard algorithm:

Input: I  = “2 + 6 * ( 3 – 4)”

Define a queue Q to record the final RPN.

Define a stack S to hold the operators.

  1. Read 2 from the infix expression, as 2 is a number, put it into Q. now Q = [2] 
  2. Read + from the infix expression, put it into the stack S, now S = [+]
  3. Read 6, as it is a number, put it into Q, now Q = [ 2, 6]
  4. Read *, as it is a operator, its left associative, and its precedence is larger than the top of S, put it into S, now S = [* , +].
  5. Read (, simply put it into the stack. now S = [ (,  * , + ]
  6. Read 3, put it into Q, now Q = [ 2, 6, 3]
  7. Read  -, the precedence of '-' is always higher than ‘ )‘, put ‘-‘ to S, now S = [ -, (, *, +]
  8. Read 4, put it into Q, now Q = [2, 6, 3, 4]
  9. Read ), now we do pop from S until we get ‘(‘ , all the popped the operators are added to Q. 
  10. Now Q = [2, 6, 3, 4, -], S = [* , +]
  11. At the end, we keep popping S, and put the elements to Q.
  12. Now Q = [2, 6, 3, 4, -, *, +], and S = [].

We print Q into a String to get the RPN: “2 6 3 4 - * +

The implementation of the shunting-yard algorithm in Java

The following code shows how to convert infix notation to RPN in Java. To make the program works in practice, it needs to do validation check, which is skipped here. 

The output: