Expression Evaluation & Parsing: Stacks, Infix/Postfix, Parsing Trees

TAKEAWAYS:

• Stacks are the core data structure for expression evaluation, handling operator precedence and parentheses.
• Infix → Postfix conversion uses a stack to reorder operators for easier evaluation (no parentheses needed).
• Postfix evaluation processes expressions left-to-right with a stack, resolving operations immediately.
• Parsing builds abstract syntax trees (ASTs) to represent expression structure for compilers/interpreters.
• Shunting-yard algorithm (Dijkstra) is the standard for infix-to-postfix conversion.
• Recursive descent parsing is a top-down method to validate and parse expressions.

Core Concepts: Stacks and Expression Evaluation

1. Stacks for Expression Evaluation

A stack is a Last-In-First-Out (LIFO) data structure where the last element added is the first one removed. For expressions, stacks store:

• Operands (numbers/variables) as they appear.
• Operators temporarily until their operands are ready.

graph LR
    A["Stack Top"] --> B["Operator: *"]
    B --> C["Operator: +"]
    C --> D["Operand: 5"]
    D --> E["Operand: 3"]
    E --> F["Stack Bottom"]

Why stacks?

• Parentheses require nested operations (LIFO).
• Operator precedence (e.g., * before +) needs delayed evaluation.
• Postfix notation eliminates parentheses entirely.

2. Infix, Postfix, and Prefix Notations

Postfix Advantage:

• No parentheses or precedence rules.
• Evaluated left-to-right with a stack.

Infix to Postfix Conversion (Shunting-Yard Algorithm)

Algorithm Steps

1. Initialize an empty stack for operators and an empty list for output.
2. Scan the infix expression left-to-right:
   • If operand, add to output.
   • If operator, pop higher/equal precedence operators to output before pushing.
   • If ‘(’, push to stack.
   • If ‘)’, pop to output until ‘(’ is found.
3. Pop remaining operators to output.

flowchart TD
    A["Start"] --> B["Read token"]
    B --> C{"Token Type?"}
    C -->|"Operand"| D["Add to output"]
    C -->|"Operator"| E["While stack top has ≥ precedence, pop to output\nPush current operator"]
    C -->|"'('"| F["Push to stack"]
    C -->|"')'"| G["Pop to output until '(' is found"]
    G --> H["Pop remaining operators to output"]
    H --> I["End"]

Worked Example: ((A + B) - C * D/E)*(H-I)*F+G

Step-by-Step Trace:

Final Postfix: A B + C D E / * H I - * F G + - *

Postfix Evaluation with a Stack

Algorithm

1. Initialize an empty stack.
2. Scan the postfix expression left-to-right:
   • If operand, push to stack.
   • If operator, pop 2 operands, apply operator, push result.
3. The final stack top is the result.

Worked Example: 4 5 + 7 3 - 2 + *

Step-by-Step Trace:

Result: 54

Parsing and Abstract Syntax Trees (ASTs)

What is an AST?

An Abstract Syntax Tree (AST) is a hierarchical representation of an expression’s structure, ignoring parentheses and operator precedence. Nodes are:

• Leaf nodes: Operands (variables/numbers).
• Internal nodes: Operators with child operands.

graph TD
    A["*"] --> B["-"]
    A --> C["+"]
    B --> D["+"]
    B --> E["*"]
    C --> F["A"]
    C --> G["B"]
    D --> H["C"]
    D --> I["D"]
    E --> J["E"]
    E --> K["/"]
    K --> L["D"]
    K --> M["E"]

Example AST for ((A + B) - C * D/E)*(H-I)*F+G:

• Root: *
  • Left child: -
    • Left: +
      • Children: A, B
    • Right: *
      • Left: C
      • Right: /
        • Left: D
        • Right: E
  • Right child: +
    • Left: *
      • Left: -
        • Children: H, I
      • Right: F
    • Right: G

Real-World Applications

1. eSewa and Kathmandu Traffic Routes (Graph + Stacks)

• eSewa’s payment processing uses stacks to handle nested transactions (e.g., deductions for bills, taxes, and fees in sequence).
• Kathmandu traffic routes can be modeled as a graph where shortest paths (e.g., from Thamel to Koteshwor) are found using Dijkstra’s algorithm, which relies on a priority queue (a variant of a stack/queue).

2. Khalti’s Loan Interest Calculation (Postfix Evaluation)

• Khalti’s loan calculator evaluates compound interest formulas like:

  A = P * (1 + r/n)^(n*t)
  

  converted to postfix for efficient computation in mobile apps.
• Example: For P=100000, r=0.05, n=12, t=5: Infix: P * (1 + r/n)^(n*t) Postfix: P 1 r n / + n t * ^ * Stack evaluation:

  Push 100000, 1, 0.05, 12, / → 1.004166...
  Push 12, 5, * → 60
  Exponentiation → 1.004166^60 ≈ 1.282
  Multiply → 100000 * 1.282 ≈ 128200
  

3. YouTube’s Video Recommendation (Parsing + Trees)

• YouTube’s recommendation engine parses user watch history (e.g., "liked" → "video1", "skipped" → "video2") into a decision tree to predict preferences.
• Example: If a user watches ["Cricket", "Football"] but skips ["Politics"], the AST might branch:

  Root: "Sports?"
    → Yes: ["Cricket", "Football"]
    → No: ["Politics" → skipped]
  

4. Ncell’s Prepaid Top-Up Validation (Recursive Descent Parsing)

• Ncell validates top-up codes like 1234-5678-9012 using recursive descent parsing to ensure:
  • Correct hyphen separation.
  • Valid digit groups (e.g., 1234 must be 4 digits).
• Example Grammar:

  TopUpCode → DigitGroup "-" DigitGroup "-" DigitGroup
  DigitGroup → Digit Digit Digit Digit
  Digit → 0|1|2|...|9
  

Comparison: Infix vs. Postfix vs. Prefix

Advantages and Disadvantages

Postfix Notation

✅ Pros:

• No parentheses or precedence rules.
• Easy to evaluate with a stack (O(n) time).
• Used in calculators (e.g., HP calculators).

❌ Cons:

• Unreadable for humans.
• Requires conversion from infix.

Abstract Syntax Trees (ASTs)

✅ Pros:

• Captures expression structure for compilers.
• Enables optimizations (e.g., constant folding).
• Used in Python’s ast module and JavaScript parsers.

❌ Cons:

• Overhead to construct and traverse.
• Not human-friendly.

Exam Tip

1. Stack Traces: Always show the stack state after each operation (e.g., infix-to-postfix conversion). Examiners love detailed traces.
2. Operator Precedence: Memorize the standard precedence:
   • Highest: Parentheses (), then *, /, %, then +, -.
3. Postfix Evaluation: For evaluation questions, write the stack contents at each step in a table.
4. ASTs: Draw the tree level by level, starting from the root operator.
5. Common Pitfalls:
   • Forgetting to pop operators of equal precedence (e.g., * and /).
   • Miscounting parentheses in infix expressions.
   • Off-by-one errors in stack indices.

Practice Question: Convert (A + B) * C - D / E to postfix and evaluate it for A=2, B=3, C=4, D=8, E=2. Show the stack states for both conversion and evaluation.