What Is Reverse Polish Notation in Data Structure With Example?

In data structure, Reverse Polish Notation (RPN) is a mathematical notation in which every operator follows all of its operands. It eliminates the need for parentheses to indicate the order of operations. RPN is also known as postfix notation.

How Does Reverse Polish Notation Work?

In RPN, instead of writing equations with operators between operands, you place the operators after the operands. Let’s consider an example to understand this concept:

Suppose we have the following infix expression: 2 + 3 * 4.

To convert this expression into RPN, we follow these steps:

1. Start scanning the infix expression from left to right.
2. If an operand is encountered, add it to the output queue.
3. If an operator is encountered:
   • If the stack is empty, push the operator onto the stack.
   • If the stack is not empty:
     • If the precedence of the current operator is greater than that of the top of the stack or they have equal precedence and are right associative (e.g., exponentiation), push the operator onto the stack.
     • Otherwise, pop operators from the stack until a lower precedence or left associative operator is encountered. Then push the current operator onto the stack.
4. If a left parenthesis “(” is encountered, push it onto the stack.
5. If a right parenthesis “)” is encountered:
   • Pop operators from the stack until a matching “(” parenthesis is encountered. Discard both “(” and “)”.Repeat steps 2-6 until the infix expression is scanned completely.
   • Pop any remaining operators from the stack and add them to the output queue.

Using the above rules, let’s convert our infix expression “2 + 3 * 4” into RPN:

Step 1: Start with an empty stack and an empty output queue.

Step 2: Scan “2”. It’s an operand, so add it to the output queue: “2”.

Step 3: Scan “+”. The stack is empty, so push “+” onto the stack.

Step 4: Scan “3”. It’s an operand, so add it to the output queue: “2 3”.

Step 5: Scan “*”.

The precedence of “*” is higher than “+”, so push “*” onto the stack.

Step 6: Scan “4”. It’s an operand, so add it to the output queue: “2 3 4”.

Note that at this stage, our infix expression has been completely scanned. Now we need to pop any remaining operators from the stack and add them to the output queue.

The stack currently contains “+”, “*”, which have higher precedence than operands in the output queue. So we pop them and add them to the output queue. The final RPN expression is: “2 3 + 4 *”.

Evaluation of Reverse Polish Notation

To evaluate an RPN expression, we start scanning the expression from left to right:

1. If an operand is encountered, push it onto the stack.
2. If an operator is encountered, pop the top two operands from the stack and apply the operator to them. Push the result back onto the stack.
3. Continue scanning until the entire expression is evaluated.

Using our previous RPN expression “2 3 + 4 *”, let’s evaluate it:

Step 1: Start with an empty stack. It’s an operand, so push it onto the stack: [2].

Step 3: Scan “3”. It’s another operand, so push it onto the stack: [2, 3].

Step 4: Scan “+”. This is an operator. Pop operands “2” and “3” from the stack.

Apply addition (2 + 3 = 5) and push the result back onto the stack: [5].

Step 5: Scan “4”. It’s another operand, so push it onto the stack: [5, 4].