Reverse Polish Notation

InterviewBuddies

·

Follow

3 min read

·

Mar 20, 2024

4

Listen

Share

Reverse Polish notation (RPN) or simply postfix notation, is a mathematical notation in which operators follow their operands.

In RPN, mathematical expressions are written in a postfix form, where operators are placed after their operands. For example, the infix expression 3 + 4 would be written as 3 4 + in RPN.

To evaluate an expression in RPN, a stack-based algorithm is commonly used. Here’s how it works:

1. Start with an empty stack.
2. Scan the expression from left to right.
3. If the current token is an operand, push it onto the stack.
4. If the current token is an operator, pop the top two operands from the stack, apply the operator to them, and push the result back onto the stack.
5. Continue this process until all tokens have been processed.
6. The final result is the value remaining on the stack.

Example

Let’s evaluate the RPN expression 3 4 + 5 *.

1. Start with an empty stack.
2. Scan the expression from left to right.

• Push 3 onto the stack (operand).
• Push 4 onto the stack (operand).
• Encounter + (operator). Pop 4 and 3, add them (3 + 4 = 7), and push 7 onto the stack.
• Push 5 onto the stack (operand).
• Encounter * (operator). Pop 5 and 7, multiply them (7 * 5 = 35), and push…