What is RPN?

Reverse Polish Notation (RPN), also called postfix notation, is a way of writing arithmetic expressions where the operator appears after its operands. It is contrasted with standard infix notation where the operator is between operands.

Why Use RPN?

• No brackets needed — precedence is unambiguous
• No precedence rules — evaluated strictly left-to-right
• Easy to evaluate with a stack — used in compilers and calculators

Converting Infix to RPN

Method 1: Expression Tree (Post-Order)

Build an expression tree from the infix expression, then perform post-order traversal.

// Infix: (3 + 4) × 2
// Expression tree (post-order traversal):
RPN: 3 4 + 2 ×

Method 2: Shunting-Yard Algorithm (Dijkstra)

// Uses: output queue + operator stack
// Rules:
// - Numbers → directly to output
// - Operators → push to stack (pop operators of >= precedence first)
// - '(' → push to stack
// - ')' → pop stack to output until '(' found

// Infix: 3 + 4 × 2
// Step by step:
// 3  → output: [3]
// +  → stack: [+]
// 4  → output: [3,4]
// ×  → × > + so push  stack: [+,×]
// 2  → output: [3,4,2]
// End→ pop stack: [3,4,2,×,+]
// RPN: 3 4 2 × +

Evaluating RPN with a Stack

// Algorithm:
// FOR each token in RPN expression:
//   IF token is a number THEN push to stack
//   IF token is an operator THEN:
//      Pop top two values (b then a)
//      Apply: result = a operator b
//      Push result back

// Example: 3 4 + 2 ×
// Token 3 → push: stack=[3]
// Token 4 → push: stack=[3,4]
// Token + → pop 4 and 3, push 7: stack=[7]
// Token 2 → push: stack=[7,2]
// Token × → pop 2 and 7, push 14: stack=[14]
// Result: 14  ✓  (same as (3+4)×2 = 14)

More RPN Examples