# What Is Reverse Polish Notation in Data Structure With Example?

//

Heather Bennett

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].

Step 6: Scan “*”. Pop operands “5” and “4” from the stack. Apply multiplication (5 * 4 = 20) and push the result back onto the stack: [20].

Note that at this stage, our RPN expression has been completely scanned. The final result is the top element of the stack, which is 20 in this case.

## Advantages of Reverse Polish Notation

• Simplicity: RPN eliminates the need for parentheses and follows a strict order of operations, making it easier to read and evaluate.
• Efficiency: RPN can be evaluated using a stack-based algorithm, which is more efficient than other approaches.
• Flexibility: RPN allows for easy extension to handle complex mathematical expressions without ambiguity.

RPN is widely used in calculators and programming languages like Forth and PostScript. It provides a concise and unambiguous way to represent mathematical expressions.

### In conclusion,

Reverse Polish Notation (RPN) is a mathematical notation in which operators follow their operands. It eliminates the need for parentheses and provides a clear order of operations.

Converting infix expressions to RPN involves scanning the expression and applying specific rules. Evaluating RPN expressions can be done efficiently using a stack-based algorithm. RPN offers simplicity, efficiency, and flexibility in representing mathematical expressions.