DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Time & Space Complexity Common Mistakes Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Expression Evaluation

Why Expression Evaluation Uses Stacks

An arithmetic expression has two fundamental challenges: operator precedence (* before +) and associativity (a - b - c means (a - b) - c, left to right). Parentheses add a third layer: explicit grouping that overrides precedence.

A stack resolves all three naturally:

LIFO order mirrors the nesting structure of expressions.
The most recently opened sub-expression must be resolved first —
exactly what parentheses demand, and exactly what a stack provides.

Three notations:
  Infix:   A + B * C   (human-readable, requires precedence rules)
  Postfix: A B C * +   (no parentheses needed, easy to evaluate)
  Prefix:  + A * B C   (no parentheses needed, recursive structure)

Postfix and prefix are unambiguous — no precedence rules required.
Evaluation of both requires only one stack pass.

Expression Notation Reference

Expression: 3 + 4 × 2 - 1

Infix:   3 + 4 * 2 - 1        (operators between operands)
Postfix: 3 4 2 * + 1 -        (operators after operands — RPN)
Prefix:  - + 3 * 4 2 1        (operators before operands — Polish)

Evaluation:
  Postfix: read left-to-right, stack operands, apply operator to top two
  Prefix:  read right-to-left, stack operands, apply operator to top two

Key insight: postfix/prefix encode precedence in their token ordering.
No parentheses or precedence rules needed during evaluation.

Part 1: Evaluate Postfix (Reverse Polish Notation)

Problem: Given a postfix expression as a token list, evaluate it and return the result.

Rule:

›Token is a number → push onto stack
›Token is an operator → pop two operands (b then a), apply a OP b, push result

CRITICAL: Pop order matters for subtraction and division.
  The top of the stack is the SECOND operand (pushed last).
  b = stack.pop()   ← right operand
  a = stack.pop()   ← left operand
  result = a OP b

Java

import java.util.Deque;
import java.util.ArrayDeque;

public class PostfixEvaluation {

    public static int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();

        for (String token : tokens) {
            switch (token) {
                case "+": {
                    int b = stack.pop(), a = stack.pop();
                    stack.push(a + b);
                    break;
                }
                case "-": {
                    int b = stack.pop(), a = stack.pop();
                    stack.push(a - b);   // a - b, not b - a
                    break;
                }
                case "*": {
                    int b = stack.pop(), a = stack.pop();
                    stack.push(a * b);
                    break;
                }
                case "/": {
                    int b = stack.pop(), a = stack.pop();
                    stack.push(a / b);   // truncates toward zero (Java int division)
                    break;
                }
                default:
                    stack.push(Integer.parseInt(token));   // Operand → push
            }
        }

        return stack.pop();   // Single remaining value is the result
    }

    public static void main(String[] args) {
        // 3 + 4 * 2 = 11
        System.out.println(evalRPN(new String[]{"3","4","2","*","+"}));         // 11
        // (3 + 4) * 2 = 14
        System.out.println(evalRPN(new String[]{"3","4","+","2","*"}));         // 14
        // 5 + ((1 + 2) * 4) - 3 = 14
        System.out.println(evalRPN(new String[]{"5","1","2","+","4","*","+","3","-"})); // 14
        // 10 / 3 = 3 (truncates toward zero)
        System.out.println(evalRPN(new String[]{"10","3","/"}));                // 3
        // -4 * 2 = -8
        System.out.println(evalRPN(new String[]{"-4","2","*"}));                // -8
    }
}

Output:
11
14
14
3
-8

Dry Run: `5 1 2 + 4 * + 3 -`

stack=[]

token '5':  push 5        stack=[5]
token '1':  push 1        stack=[5,1]
token '2':  push 2        stack=[5,1,2]
token '+':  b=2, a=1  → 1+2=3,  push 3   stack=[5,3]
token '4':  push 4        stack=[5,3,4]
token '*':  b=4, a=3  → 3*4=12, push 12  stack=[5,12]
token '+':  b=12,a=5  → 5+12=17,push 17  stack=[17]
token '3':  push 3        stack=[17,3]
token '-':  b=3, a=17 → 17-3=14,push 14  stack=[14]

Result: 14 ✓

Why b is popped FIRST:
  The expression a - b has b on top (it was pushed after a).
  Popping b first then a gives us the correct operand order.
  Getting this wrong turns "17 - 3" into "3 - 17 = -14".

Part 2: Infix to Postfix Conversion (Shunting-Yard Algorithm)

Problem: Convert a human-readable infix expression to postfix notation.

Dijkstra's Shunting-Yard algorithm:

›Operand → append to output
›( → push to operator stack
›) → pop and output until ( is found; discard the (
›Operator → pop and output all operators of ≥ precedence (left-associative), then push
›End → pop all remaining operators to output

Operator precedence table:
  ^  (exponentiation) → 3, right-associative
  *  /                → 2, left-associative
  +  -                → 1, left-associative

Java

import java.util.Deque;
import java.util.ArrayDeque;

public class InfixToPostfix {

    private static int precedence(char op) {
        if (op == '^')            return 3;
        if (op == '*' || op == '/') return 2;
        if (op == '+' || op == '-') return 1;
        return -1;
    }

    private static boolean isRightAssociative(char op) {
        return op == '^';
    }

    public static String infixToPostfix(String infix) {
        Deque<Character> opStack = new ArrayDeque<>();
        StringBuilder    output  = new StringBuilder();

        for (int i = 0; i < infix.length(); i++) {
            char c = infix.charAt(i);
            if (c == ' ') continue;

            if (Character.isLetterOrDigit(c)) {
                // Multi-digit number support
                output.append(c);
                // Check if next char is also a digit
                if (i + 1 < infix.length() && Character.isDigit(infix.charAt(i + 1))) {
                    continue;   // Will be appended next iteration
                }
                output.append(' ');

            } else if (c == '(') {
                opStack.push(c);

            } else if (c == ')') {
                // Pop to output until matching '('
                while (!opStack.isEmpty() && opStack.peek() != '(') {
                    output.append(opStack.pop()).append(' ');
                }
                opStack.pop();   // Discard '('

            } else {
                // Operator: pop higher/equal precedence (respecting associativity)
                while (!opStack.isEmpty()
                       && opStack.peek() != '('
                       && (precedence(opStack.peek()) > precedence(c)
                           || (precedence(opStack.peek()) == precedence(c)
                               && !isRightAssociative(c)))) {
                    output.append(opStack.pop()).append(' ');
                }
                opStack.push(c);
            }
        }

        while (!opStack.isEmpty()) {
            output.append(opStack.pop()).append(' ');
        }

        return output.toString().trim();
    }

    public static void main(String[] args) {
        System.out.println(infixToPostfix("A+B*C"));           // A B C * +
        System.out.println(infixToPostfix("(A+B)*C"));         // A B + C *
        System.out.println(infixToPostfix("A+B*C-D/E"));       // A B C * + D E / -
        System.out.println(infixToPostfix("A^B^C"));           // A B C ^ ^ (right assoc)
        System.out.println(infixToPostfix("(A+B)*(C-D)/(E+F)")); // A B + C D - * E F + /
    }
}

Output:
A B C * +
A B + C *
A B C * + D E / -
A B C ^ ^
A B + C D - * E F + /

Dry Run: `A+B*C-D/E`

opStack=[], output=[]

'A':  operand   → output=[A]
'+':  prec(+)=1, stack empty → push  opStack=[+]
'B':  operand   → output=[A,B]
'*':  prec(*)=2 > prec(+)=1  → no pop → push   opStack=[+,*]
'C':  operand   → output=[A,B,C]
'-':  prec(-)=1
       prec(*)=2 ≥ 1 → pop * → output=[A,B,C,*]  opStack=[+]
       prec(+)=1 ≥ 1 → pop + → output=[A,B,C,*,+] opStack=[]
       push -                                       opStack=[-]
'D':  operand   → output=[A,B,C,*,+,D]
'/':  prec(/)=2 > prec(-)=1 → no pop → push  opStack=[-,/]
'E':  operand   → output=[A,B,C,*,+,D,E]

End: pop remaining stack:
  pop /  → output=[A,B,C,*,+,D,E,/]   opStack=[-]
  pop -  → output=[A,B,C,*,+,D,E,/,-] opStack=[]

Result: A B C * + D E / -

Verify: A + B*C - D/E
  B*C first (prec), then A+result, then D/E, then subtract.
  Postfix encodes this order exactly without parentheses.

Part 3: Infix to Prefix Conversion

Problem: Convert infix to prefix notation (Polish Notation). Operators precede their operands.

Algorithm:

›Reverse the infix expression
›Swap ( and ) in the reversed string
›Apply infix-to-postfix on the modified string
›Reverse the result

Why this works:
  Prefix is the mirror image of postfix.
  Reversing + swapping brackets converts the problem to a postfix problem.
  Reversing the result gives prefix.

Java

public class InfixToPrefix {

    private static int precedence(char op) {
        if (op == '^')              return 3;
        if (op == '*' || op == '/') return 2;
        if (op == '+' || op == '-') return 1;
        return -1;
    }

    private static String toPostfixForPrefix(String s) {
        java.util.Deque<Character> opStack = new java.util.ArrayDeque<>();
        StringBuilder output = new StringBuilder();

        for (char c : s.toCharArray()) {
            if (c == ' ') continue;

            if (Character.isLetterOrDigit(c)) {
                output.append(c).append(' ');

            } else if (c == '(') {   // Already swapped from ')'
                opStack.push(c);

            } else if (c == ')') {   // Already swapped from '('
                while (!opStack.isEmpty() && opStack.peek() != '(') {
                    output.append(opStack.pop()).append(' ');
                }
                if (!opStack.isEmpty()) opStack.pop();

            } else {
                // For prefix: right-associative treatment (pop only strictly greater)
                while (!opStack.isEmpty()
                       && opStack.peek() != '('
                       && precedence(opStack.peek()) > precedence(c)) {
                    output.append(opStack.pop()).append(' ');
                }
                opStack.push(c);
            }
        }

        while (!opStack.isEmpty()) {
            output.append(opStack.pop()).append(' ');
        }
        return output.toString().trim();
    }

    public static String infixToPrefix(String infix) {
        // Step 1: Reverse the expression
        String reversed = new StringBuilder(infix).reverse().toString();

        // Step 2: Swap brackets
        StringBuilder swapped = new StringBuilder();
        for (char c : reversed.toCharArray()) {
            if      (c == '(') swapped.append(')');
            else if (c == ')') swapped.append('(');
            else               swapped.append(c);
        }

        // Step 3: Apply modified postfix conversion
        String postfix = toPostfixForPrefix(swapped.toString());

        // Step 4: Reverse the result
        return new StringBuilder(postfix).reverse().toString().trim();
    }

    public static void main(String[] args) {
        System.out.println(infixToPrefix("A+B*C"));           // + A * B C
        System.out.println(infixToPrefix("(A+B)*C"));         // * + A B C
        System.out.println(infixToPrefix("A+B*C-D/E"));       // - + A * B C / D E
        System.out.println(infixToPrefix("(A+B)*(C-D)"));     // * + A B - C D
    }
}

Output:
+ A * B C
* + A B C
- + A * B C / D E
* + A B - C D

Part 4: Evaluate Prefix Expression

Problem: Given a prefix expression as a token list, evaluate it.

Rule: Read tokens right to left (opposite of postfix).

›Token is a number → push onto stack
›Token is an operator → pop two operands (a then b), apply a OP b, push result

Why right to left?
  In prefix, the operator comes before its operands.
  Reading right to left gives operands before their operator —
  exactly the same as postfix read left to right.
  The first pop gives the LEFT operand (a), second pop gives RIGHT (b).

Java

import java.util.Deque;
import java.util.ArrayDeque;

public class PrefixEvaluation {

    public static int evalPrefix(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();

        // Process right to left
        for (int i = tokens.length - 1; i >= 0; i--) {
            String token = tokens[i];

            if (token.equals("+") || token.equals("-")
                    || token.equals("*") || token.equals("/")) {
                int a = stack.pop();   // LEFT operand (first popped when reading RTL)
                int b = stack.pop();   // RIGHT operand
                switch (token) {
                    case "+": stack.push(a + b); break;
                    case "-": stack.push(a - b); break;
                    case "*": stack.push(a * b); break;
                    case "/": stack.push(a / b); break;
                }
            } else {
                stack.push(Integer.parseInt(token));
            }
        }

        return stack.pop();
    }

    public static void main(String[] args) {
        // + 3 * 4 2  =  3 + 4*2  = 11
        System.out.println(evalPrefix(new String[]{"+","3","*","4","2"}));        // 11
        // * + 3 4 2  =  (3+4)*2  = 14
        System.out.println(evalPrefix(new String[]{"*","+","3","4","2"}));        // 14
        // - + 5 * 1 4 3  =  5 + 1*4 - 3 = 6
        System.out.println(evalPrefix(new String[]{"-","+","5","*","1","4","3"})); // 6
        // - + A * B C / D E  — symbolic (can't eval letters, but shows structure)
    }
}

Output:
11
14
6

Dry Run: Prefix `* + 3 4 2` (= (3+4)×2 = 14)

tokens = ["*", "+", "3", "4", "2"]
Read right to left:

i=4: '2'  → push 2    stack=[2]
i=3: '4'  → push 4    stack=[2,4]
i=2: '3'  → push 3    stack=[2,4,3]
i=1: '+'  → a=pop()=3 (left), b=pop()=4 (right) → 3+4=7, push 7
            stack=[2,7]
i=0: '*'  → a=pop()=7 (left), b=pop()=2 (right) → 7*2=14, push 14
            stack=[14]

Result: 14 ✓

Why a is the LEFT operand here:
  Reading right-to-left, the rightmost operand is pushed first.
  When the operator is reached, the left operand is on top
  (it was the closest one to the right of the operator).
  So first pop = left, second pop = right.

Part 5: Evaluate Arithmetic Expression String

Problem: Given an infix arithmetic string like "3 + 4 * 2" or "(1+(4+5+2)-3)+(6+8)", evaluate it directly without first converting to postfix.

Algorithm (two-stack method):

›One stack for operands (numbers)
›One stack for operators
›When an operator with higher or equal precedence is on the operator stack, evaluate it immediately

Java

import java.util.Deque;
import java.util.ArrayDeque;

public class EvaluateInfixString {

    private static int precedence(char op) {
        if (op == '+' || op == '-') return 1;
        if (op == '*' || op == '/') return 2;
        return 0;
    }

    private static int applyOp(int a, int b, char op) {
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/': return a / b;
        }
        return 0;
    }

    public static int evaluate(String s) {
        Deque<Integer> nums = new ArrayDeque<>();
        Deque<Character> ops = new ArrayDeque<>();
        int i = 0;

        while (i < s.length()) {
            char c = s.charAt(i);

            if (c == ' ') { i++; continue; }

            if (Character.isDigit(c)) {
                // Parse multi-digit number
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                nums.push(num);
                continue;   // i already advanced

            } else if (c == '(') {
                ops.push(c);

            } else if (c == ')') {
                // Evaluate everything inside the parentheses
                while (!ops.isEmpty() && ops.peek() != '(') {
                    int b = nums.pop(), a = nums.pop();
                    nums.push(applyOp(a, b, ops.pop()));
                }
                ops.pop();   // Discard '('

            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                // Evaluate operators with >= precedence before pushing
                while (!ops.isEmpty() && ops.peek() != '('
                       && precedence(ops.peek()) >= precedence(c)) {
                    int b = nums.pop(), a = nums.pop();
                    nums.push(applyOp(a, b, ops.pop()));
                }
                ops.push(c);
            }

            i++;
        }

        // Evaluate remaining operators
        while (!ops.isEmpty()) {
            int b = nums.pop(), a = nums.pop();
            nums.push(applyOp(a, b, ops.pop()));
        }

        return nums.pop();
    }

    public static void main(String[] args) {
        System.out.println(evaluate("3 + 4 * 2"));               // 11
        System.out.println(evaluate("(3 + 4) * 2"));             // 14
        System.out.println(evaluate("(1+(4+5+2)-3)+(6+8)"));     // 23
        System.out.println(evaluate("100 * 2 + 12"));            // 212
        System.out.println(evaluate("100 * ( 2 + 12 )"));        // 1400
        System.out.println(evaluate("100 * ( 2 + 12 ) / 14"));   // 100
    }
}

Output:
11
14
23
100

Dry Run: `"3 + 4 * 2"` → 11

nums=[], ops=[]

'3':   digit → num=3, push    nums=[3]         ops=[]
' ':   skip
'+':   prec(+)=1, ops empty → push +           nums=[3]    ops=[+]
' ':   skip
'4':   digit → num=4, push    nums=[3,4]        ops=[+]
' ':   skip
'*':   prec(*)=2 > prec(+)=1 → no pop → push * nums=[3,4]  ops=[+,*]
' ':   skip
'2':   digit → num=2, push    nums=[3,4,2]      ops=[+,*]

End of string — drain ops:
  pop *: b=2, a=4 → 4*2=8, push 8  nums=[3,8]  ops=[+]
  pop +: b=8, a=3 → 3+8=11,push 11 nums=[11]   ops=[]

Result: 11 ✓

Notation Comparison and Complexity

                  Infix          Postfix         Prefix
Example:         A + B * C      A B C * +       + A * B C
Parentheses:     Required       Never needed    Never needed
Human readability: High         Low             Very low
Evaluation:      Complex        O(n) one stack  O(n) one stack RTL
Conversion from  —              O(n) Shunting   O(n) via postfix
infix:
Recursive struct: Natural       Iterative easy  Mirrors recursion

Operation	Time	Space	Notes
Evaluate postfix	O(n)	O(n)	One stack, single pass
Evaluate prefix	O(n)	O(n)	One stack, right-to-left
Infix → postfix	O(n)	O(n)	Shunting-yard algorithm
Infix → prefix	O(n)	O(n)	Reverse + shunting + reverse
Evaluate infix string	O(n)	O(n)	Two stacks, single pass

Common Mistakes

Wrong operand pop order in postfix. When applying an operator, the right operand is on top (it was pushed last). Always pop b first (right), then a (left). For a - b, getting this wrong returns b - a — produces wrong answers for subtraction and division, correct for addition and multiplication (both commutative).

Using int division instead of truncation toward zero. Python's int(a / b) truncates toward zero. Python's floor division a // b truncates toward negative infinity. For eval_rpn(["-7","2","/"]), the LeetCode spec expects -3 (truncate toward zero), not -4 (floor). Always use int(a / b) or Math.trunc(a / b) for postfix evaluation problems.

Not handling multi-digit numbers in infix evaluation. Reading one character at a time breaks on "123 + 4". Always collect digits in a loop until the next character is not a digit before pushing the number to the operand stack.

Skipping the '(' guard in the operator pop loop. The operator pop loop must stop at '(' — never pop a ( as an operator. Omitting ops.peek() != '(' causes parenthesised sub-expressions to be evaluated prematurely.

Not clearing redo stack — actually, not draining the operator stack after input ends. After reading all tokens, the operator stack may still contain operators. Always drain it completely: while (!ops.isEmpty()) { evaluate top two nums with top op }.

Interview Questions

Q: Why does postfix evaluation never need parentheses?

Postfix encodes operator precedence in the ordering of tokens. In A B C * +, the * appears after both its operands B and C and before +. When evaluated left to right with a stack, * is always applied to B and C before + gets to use the result — exactly what A + B * C means. The token order makes precedence unambiguous without any special rules or symbols.

Q: Why must the infix-to-prefix algorithm reverse the string before applying the postfix algorithm?

Prefix is the mirror image of postfix — the operator precedes its operands instead of following them. Reversing the input string converts each prefix sub-expression into a postfix sub-expression (the operands appear before the operator when read left to right). Swapping brackets maintains the correct grouping in the reversed order. Reversing the output then mirrors postfix back to prefix. This avoids writing a separate algorithm from scratch.

Q: What is the difference between the one-stack postfix evaluator and the two-stack infix evaluator?

Postfix is already linearised — no precedence resolution is needed at evaluation time. One stack for operands suffices: push numbers, apply operators to the top two immediately. Infix requires deferring operators until higher-precedence operations complete. Two stacks — one for operands, one for operators — let the algorithm peek at the top operator's precedence before deciding whether to apply it or defer it. The two-stack approach is essentially inline Shunting-Yard + evaluation in one pass.

FAQs

Can these algorithms handle unary minus (negative numbers like -4)?

Simple implementations handle negative number tokens ("-4" as a pre-tokenised string) but not unary minus in expressions like "-4 + 2" as a character sequence. For unary minus in infix strings, handle c == '-' at the start of the string or immediately after ( as a sign, not an operator. Push 0 first, then the - operator, so "-4" becomes 0 - 4. Alternatively, pre-tokenise the string to identify sign vs subtraction.

What is associativity and why does it matter for ^?

Associativity determines how equal-precedence operators group. Left-associative: a - b - c = (a - b) - c. Right-associative: a ^ b ^ c = a ^ (b ^ c). For left-associative operators, pop when the stack top has equal or greater precedence. For right-associative (^), only pop when the stack top has strictly greater precedence — equal precedence means "group right first." Without this distinction, 2^3^2 would be computed as (2^3)^2 = 64 instead of 2^(3^2) = 512.

When would you use prefix notation in practice?

Prefix notation (Polish notation) is used in LISP and Scheme programming languages where all expressions are written as (operator operands...). It is also used in some calculators, compilers for AST serialisation, and certain logic systems. Its advantage is that recursive evaluation is extremely natural — an evaluator can be written as a single recursive function that reads the operator, evaluates two sub-expressions, and applies the operator. Postfix is used in stack-based virtual machines (JVM bytecode, PostScript, Forth).

Quick Quiz

Question 1: Evaluate postfix 8 2 / 3 -. What is the result?

›A) 1
›B) 4
›C) -1
›D) 7

Answer: A) 1. 8 2 / → b=2, a=8 → 8/2=4, push 4. 4 3 - → b=3, a=4 → 4-3=1. Result: 1.

Question 2: In postfix evaluation, for operator -, which value is popped first?

›A) The left operand (pushed first, deeper in stack)
›B) The right operand (pushed last, on top)
›C) Either — subtraction is commutative
›D) The smaller value

Answer: B) The right operand is popped first. The right operand was pushed last so it sits on top. Pop b (right) first, then a (left). Compute a - b. Reversing gives b - a — wrong for all non-symmetric operations.

Question 3: Converting A^B^C to postfix should give A B C ^ ^ (right-associative). What would happen if ^ were treated as left-associative?

›A) The result would be the same — associativity doesn't affect postfix
›B) It would produce A B ^ C ^, evaluating as (A^B)^C instead of A^(B^C)
›C) It would produce a syntax error
›D) It would produce A B C ^ +

Answer: B) A B ^ C ^, evaluating as (A^B)^C. Left-associative processing pops ^ from the stack when a new ^ arrives (equal precedence triggers a pop). This produces A B ^ C ^ which evaluates (A^B)^C. Right-associative processing does NOT pop on equal precedence, leaving both ^ operators on the stack to be popped in the correct right-to-left order, giving A B C ^ ^ which evaluates A^(B^C).

Question 4: The two-stack infix evaluator needs to evaluate "(3 + 4) * 2". At what point does the + operation get applied?

›A) When + is pushed to the ops stack
›B) When * is encountered and has higher precedence than +
›C) When ) is encountered, which triggers evaluation until ( is found
›D) At the end when the ops stack is drained

Answer: C) When ) is encountered. The ) triggers a loop that pops and evaluates operators until ( is found. At that point, + pops, applies to 3 and 4 giving 7, which is pushed to nums. Then ( is discarded. Now * applies to 7 and 2 giving 14.

Summary

Expression evaluation with stacks covers five distinct problems, each with a specific algorithm:

Evaluate postfix (RPN): Single stack, left to right. Numbers → push. Operator → pop b (right), pop a (left), apply a OP b, push result. O(n) time, O(n) space.

Infix to postfix (Shunting-Yard): Operator stack tracks deferred operators. Operands go directly to output. ( pushes to stack. ) pops to output until (. Operators pop equal/higher-precedence before pushing. End → drain stack. Handles left and right associativity.

Infix to prefix: Reverse input, swap brackets, apply modified postfix conversion (pop only strictly greater, not equal), reverse the result tokens.

Evaluate prefix: Single stack, right to left. Numbers → push. Operator → pop a (left), pop b (right), apply a OP b, push result.

Evaluate infix string directly: Two stacks — operands and operators. Same operator-precedence logic as Shunting-Yard, but immediately apply whenever a lower-precedence operator arrives or ) is encountered.

Critical correctness points: pop order determines operand assignment for non-commutative operators; right-associativity requires > not >= in the pop condition; multi-digit numbers require a digit-collection loop; the ops stack must be fully drained after all input is consumed.

←

PreviousBalanced Parentheses

NextMonotonic Stack

→