Postfix Notation (Reverse Polish Notation or RPN)

Infix Notation:
Infix notation is the standard arithmetic notation where operators are positioned between operands within an expression. This format is familiar in everyday mathematics and serves as the conventional way humans read and write mathematical operations.
Eg : ((7 + 3) * (4 - 2)) / 5

Prefix Notation (Polish notation):
Prefix notation is the notation in which operators are placed before the corresponding operands in the expression.
Eg :/ * + 7 3–4 2 5

Postfix Notation (Reverse Polish Notation or RPN)

Postfix Notation (Reverse Polish Notation):
Postfix notation is the notation in which operators are placed after the corresponding operands in the expression.
Eg :7 3 + 4 2 — * 5 /

Infix notation: A + B
Postfix notation: AB+
Prefix notation : +AB

• Postfix notation is also called as ‘suffix notation’ and ‘reverse polish’.
• In the postfix notation, any expression can be written unambiguously without parentheses.
• The ordinary (infix) way of writing the sum of x and y is with operator in the middle: x * y. But in the postfix notation, we place the operator at the right end as xy *.
• In postfix notation, the operator follows the operand.

Advantages of Postfix over Prefix Notations:

• Postfix notation has fewer overheads of parenthesis. i.e., it takes less time for parsing.
• Postfix expressions can be evaluated easily as compared to other notations.

Example 1: Addition

• Infix: 3 + 4
• Postfix: 3 4 +
• Explanation: In postfix notation, 3 4 + means "add 3 to 4". The + operator follows its operands (3 and 4).

Example 2: Subtraction

• Infix: 8 - 5
• Postfix: 8 5 -
• Explanation: In postfix notation, 8 5 - means "subtract 5 from 8". The - operator follows its operands (8 and 5).

Example 3: Multiplication

• Infix: 2 * 6
• Postfix: 2 6 *
• Explanation: In postfix notation, 2 6 * means "multiply 2 by 6". The * operator follows its operands (2 and 6).

Example 4: Division

• Infix: 10 / 2
• Postfix: 10 2 /
• Explanation: In postfix notation, 10 2 / means "divide 10 by 2". The / operator follows its operands (10 and 2).

Example 5: Complex Expression

• Infix: (3 + 4) * (6 - 2)
• Postfix: 3 4 + 6 2 - *
• Explanation:
  – Convert each part:
  – 3 + 4 in postfix becomes 3 4 +.
  – 6 - 2 in postfix becomes 6 2 -.
  – Combine both parts with * in postfix notation: 3 4 + 6 2 - *.
• Evaluation steps:
  –Push 3 and 4 onto the stack.
  –Encounter +: Pop 3 and 4, compute 3 + 4 = 7, push 7 onto the stack.
  –Push 6 and 2 onto the stack.
  –Encounter -: Pop 6 and 2, compute 6 - 2 = 4, push 4 onto the stack.
  –Encounter *: Pop 7 and 4, compute 7 * 4 = 28, push 28 onto the stack.
  –Result: 28.

Example 6: More Complex Expression with Parentheses

• Infix: 5 + ((1 + 2) * 4) - 3
• Postfix: 5 1 2 + 4 * + 3 -
• Explanation:
• Convert each part:
  –1 + 2 in postfix becomes 1 2 +.
  –(1 + 2) * 4 in postfix becomes 1 2 + 4 *.
  –Combine with + and - operators in postfix notation: 5 1 2 + 4 * +3-
• Evaluation steps:
  –Push 5 onto the stack.
  –Push 1 and 2 onto the stack.
  –Encounter +: Pop 1 and 2, compute 1 + 2 = 3, push 3 onto the stack.
  –Push 4 onto the stack.
  –Encounter *: Pop 3 and 4, compute 3 * 4 = 12, push 12 onto the stack.
  –Encounter +: Pop 5 and 12, compute 5 + 12 = 17, push 17 onto the stack.
  –Push 3 onto the stack.
  –Encounter -: Pop 17 and 3, compute 17 - 3 = 14, push 14 onto the stack.
  –Result: 14.