Prefix/Infix/Postfix Notation
Three ways of writing the same expression, and how to convert and evaluate them.
Overview
Prefix, infix, and postfix notations are different ways of writing mathematical expressions. Each has its own advantages and is particularly useful in specific contexts in computer science.
Key Concepts:
- Infix Notation: The standard mathematical notation where operators are placed between operands (e.g., 5 + 3)
- Prefix Notation: Also known as Polish notation, where operators are placed before operands (e.g., + 5 3)
- Postfix Notation: Also known as Reverse Polish notation, where operators are placed after operands (e.g., 5 3 +)
Key Concepts
Infix Notation
This is the standard mathematical notation we use in everyday calculations. While it's the most natural for humans to read, it requires precedence rules and parentheses to avoid ambiguity.
Order of Precedence (PEMDAS):
- Parentheses
- Exponentiation
- Multiplication and Division (left to right)
- Addition and Subtraction (left to right)
Prefix Notation (Polish Notation)
In prefix notation, the operator is placed before its operands. This notation eliminates the need for parentheses and operator precedence rules.
Postfix Notation (Reverse Polish Notation)
In postfix notation, the operator follows its operands. Like prefix notation, it eliminates the need for parentheses and operator precedence rules.
Converting Prefix and Postfix to Infix
Converting prefix and postfix expressions to infix notation is useful for understanding and verifying expressions. The key is to work systematically, identifying operators and their operands.
Key Tips:
- Prefix: Read right to left. Each operator applies to the two operands immediately following it.
- Postfix: Read left to right. Each operator applies to the two operands immediately preceding it.
- Always add parentheses around each operation to maintain the correct order of operations in infix notation.
Examples
5 + 8/(3-1)
Evaluation steps:
- Evaluate parentheses: (3-1) = 2
- Perform division: 8/2 = 4
- Perform addition: 5 + 4 = 9
5 + 8/(3-1) → + 5 / 8 - 3 1
Steps for conversion:
- Start with fully parenthesized infix:
(5 + (8 / (3 - 1))) - Convert innermost parentheses first:
(3 - 1)→- 3 1 - Convert next operation:
(8 / (- 3 1))→/ 8 - 3 1 - Convert final operation:
(5 + (/ 8 - 3 1))→+ 5 / 8 - 3 1
5 + 8/(3-1) → 5 8 3 1 - / +
Steps for conversion:
- Start with fully parenthesized infix:
(5 + (8 / (3 - 1))) - Convert innermost parentheses first:
(3 - 1)→3 1 - - Convert next operation:
(8 / (3 1 -))→8 3 1 - / - Convert final operation:
(5 + (8 3 1 - /))→5 8 3 1 - / +
+ * 5 3 / 8 2
Method: Read from right to left, identify operators and their operands:
- Start from the rightmost operator:
/
Find its two operands:8and2
Convert:/ 8 2→(8 / 2) - Move left to next operator:
*
Find its two operands:5and3
Convert:* 5 3→(5 * 3) - Final operator:
+
Find its two operands:(5 * 3)and(8 / 2)
Convert:+ (5 * 3) (8 / 2)→((5 * 3) + (8 / 2))
Result: ((5 * 3) + (8 / 2)) = 15 + 4 = 19
5 3 * 8 2 / +
Method: Read from left to right, identify operators and their operands:
- Start from the leftmost operator:
*
Find its two operands (immediately before it):5and3
Convert:5 3 *→(5 * 3) - Move right to next operator:
/
Find its two operands:8and2
Convert:8 2 /→(8 / 2) - Final operator:
+
Find its two operands:(5 * 3)and(8 / 2)
Convert:(5 * 3) (8 / 2) +→((5 * 3) + (8 / 2))
Result: ((5 * 3) + (8 / 2)) = 15 + 4 = 19
Practice Problems
Problem 1 Junior
Convert the following infix expression to prefix notation (Write answer with no spaces; you may type ^ or ↑ for exponentiation):
(A * B - C / D) ↑ E
Solution
To convert from infix to prefix, we work from the innermost operations outward:
- Start with fully parenthesized expression:
((A * B) - (C / D)) ↑ E - Convert innermost operations first:
(A * B)→* A B(C / D)→/ C D - Convert the subtraction:
((* A B) - (/ C D))→- * A B / C D - Convert the exponentiation:
((- * A B / C D) ↑ E)→↑ - * A B / C D E
Answer: ^ - * A B / C D E
Problem 2 Junior
Evaluate the following postfix expression:
5 3 + 2 * 1 -
Solution
To evaluate a postfix expression, read from left to right and apply operators to the two most recent operands:
- Read
5→ stack: [5] - Read
3→ stack: [5, 3] - Read
+→ pop 3 and 5, compute 5 + 3 = 8, push 8 → stack: [8] - Read
2→ stack: [8, 2] - Read
*→ pop 2 and 8, compute 8 * 2 = 16, push 16 → stack: [16] - Read
1→ stack: [16, 1] - Read
-→ pop 1 and 16, compute 16 - 1 = 15, push 15 → stack: [15]
Answer: 15
Problem 3 Intermediate
Evaluate the following prefix expression:
↑ + * 3 4 / 8 2 - 7 5
Solution
To convert from prefix to infix, read from right to left and work from the outermost operation inward:
- Start with:
↑ + * 3 4 / 8 2 - 7 5 - The outermost operator is
↑, so we need two operands:
Left operand:+ * 3 4 / 8 2
Right operand:- 7 5 - Convert right operand:
- 7 5→(7 - 5)=2 - Convert left operand:
+ * 3 4 / 8 2
Left:* 3 4→(3 * 4)=12
Right:/ 8 2→(8 / 2)=4
So:+ 12 4→(12 + 4)=16 - Final:
↑ 16 2→(16 ↑ 2)=16²=256
Infix form: ((3 * 4) + (8 / 2)) ↑ (7 - 5)
Answer: 256