Expression Evaluation - Infix, Postfix, and Prefix Notation

Expression evaluation was initially one of the most confusing topics for me in DSA. I kept thinking, "Why can't we just evaluate expressions left to right?" But once I understood operator precedence, associativity, and how different notations eliminate ambiguity, the beauty of postfix and prefix notation became clear. Let me share what I've learned about these fundamental algorithms.

Introduction to Expression Notation

When I first encountered different expression notations, I was puzzled why we needed anything other than the familiar infix notation (like 2 + 3 * 4). But then I learned that infix expressions are actually ambiguous without precedence rules, and that postfix and prefix notations eliminate this ambiguity entirely!

Expression evaluation involves computing the value of mathematical expressions written in different notations. The three main notations are:

• Infix: Operator between operands (2 + 3)
• Postfix (RPN): Operator after operands (2 3 +)
• Prefix (Polish): Operator before operands (+ 2 3)

Understanding the Problem

Ambiguity in Infix Notation

Expression: 2 + 3 * 4

Two possible interpretations:

1. (2 + 3) * 4 = 20
2. 2 + (3 * 4) = 14

Solution: Operator precedence and associativity rules

• Multiplication has higher precedence than addition
• Same precedence operators are left-associative (usually)
• Result: 2 + (3 * 4) = 14

Why Postfix and Prefix?

Advantages:

• No ambiguity - no need for precedence rules
• No parentheses needed
• Easy to evaluate using a stack
• Natural for computer processing

I remember being amazed that such simple notations could eliminate all the complexity of precedence rules!

Postfix (Reverse Polish) Notation

Definition and Examples

Postfix notation: Operators come after their operands.

Examples:

Infix: 2 + 3        Postfix: 2 3 +
Infix: 2 + 3 * 4    Postfix: 2 3 4 * +
Infix: (2 + 3) * 4  Postfix: 2 3 + 4 *
Infix: 2 * 3 + 4    Postfix: 2 3 * 4 +

Postfix Evaluation Example

Expression: "2 3 4 * +"

Step-by-step execution:

Token: 2    Stack: [2]
Token: 3    Stack: [2, 3]
Token: 4    Stack: [2, 3, 4]
Token: *    Pop 4, 3; Push 3*4=12    Stack: [2, 12]
Token: +    Pop 12, 2; Push 2+12=14  Stack: [14]

Result: 14

Prefix (Polish) Notation

Definition and Examples

Prefix notation: Operators come before their operands.

Examples:

Infix: 2 + 3        Prefix: + 2 3
Infix: 2 + 3 * 4    Prefix: + 2 * 3 4
Infix: (2 + 3) * 4  Prefix: * + 2 3 4
Infix: 2 * 3 + 4    Prefix: + * 2 3 4

Prefix Evaluation Algorithm

Algorithm:

1. Scan expression from right to left
2. If operand, push to stack
3. If operator, pop required operands, compute, push result
4. Final stack element is the result

Prefix Evaluation Example

Expression: "+ 2 * 3 4"

Step-by-step execution (right to left):

Token: 4    Stack: [4]
Token: 3    Stack: [4, 3]
Token: *    Pop 4, 3; Push 4*3=12    Stack: [12]
Token: 2    Stack: [12, 2]
Token: +    Pop 12, 2; Push 12+2=14  Stack: [14]

Result: 14

Infix to Postfix Conversion

Shunting Yard Algorithm

Algorithm (Dijkstra's Shunting Yard):

1. Create output queue and operator stack
2. For each token:
   • If operand: add to output
   • If operator: handle precedence and associativity
   • If '(': push to stack
   • If ')': pop until '('
3. Pop remaining operators to output

Conversion Example

Expression: "2 + 3 * 4"

Step-by-step conversion:

Token: 2    Output: [2]           Stack: []
Token: +    Output: [2]           Stack: [+]
Token: 3    Output: [2, 3]        Stack: [+]
Token: *    Output: [2, 3]        Stack: [+, *]  (* has higher precedence)
Token: 4    Output: [2, 3, 4]     Stack: [+, *]
End:        Output: [2, 3, 4, *, +] Stack: []

Result: "2 3 4 * +"

I found tracing through these examples step-by-step really helped me understand the algorithm!

Infix to Prefix Conversion

Algorithm

Method 1: Reverse and Modify

1. Reverse the infix expression
2. Replace '(' with ')' and vice versa
3. Convert to postfix
4. Reverse the result

Time and Space Complexity

Time Complexity

Where n is the number of tokens in the expression.

Space Complexity

Applications and Use Cases

Compiler Design

Expression parsing in compilers:

• Convert infix to postfix for easier evaluation
• Generate assembly code from postfix
• Optimize expression evaluation

Calculator Applications

Scientific calculators:

• Parse user input (infix)
• Convert to postfix internally
• Evaluate using stack

Spreadsheet Software

Formula evaluation:

• Parse cell formulas
• Handle operator precedence
• Support function calls

Mathematical Software

Computer algebra systems:

• Parse mathematical expressions
• Symbolic computation
• Expression simplification

Practice Problems

Here are some problems I found helpful during preparation:

1. Basic Calculator - Evaluate simple arithmetic expressions
2. Calculator with Parentheses - Handle nested parentheses
3. Reverse Polish Notation - Evaluate RPN expressions
4. Expression Tree - Build and evaluate expression trees
5. Basic Calculator III - Handle functions and advanced operators

Conclusion

Expression evaluation is a fundamental topic that demonstrates the power of stack-based algorithms. Key takeaways:

Core Concepts:

• Three notations: infix, postfix, prefix
• Stack-based evaluation algorithms
• Operator precedence and associativity

Algorithms:

• Shunting Yard for infix to postfix conversion
• Stack-based evaluation for postfix and prefix
• Direct infix evaluation using conversion

Applications:

• Compiler design and parsing
• Calculator implementations
• Mathematical software
• Spreadsheet formula evaluation

For loksewa preparation, focus on:

• Understanding all three notations
• Implementing conversion algorithms
• Stack-based evaluation techniques
• Handling operator precedence correctly
• Error handling and edge cases

Remember: The key insight is that postfix and prefix notations eliminate ambiguity by encoding operator precedence in the structure itself. This makes them ideal for computer processing, even though infix is more natural for humans.

Understanding these algorithms provides a foundation for more advanced topics like parsing, compiler design, and symbolic computation!