Chapter 30 of 65

Stack Applications (Expression Conversion & Monotonic Stack)

On this page

In the previous chapter you learned what a stack is: a LIFO structure with push, pop and peek, all in O(1). You also saw one classic use, checking balanced brackets.

Now let's look at two families of problems where stacks really shine, and which appear again and again in university exams and placement interviews:

  1. Expression conversion and evaluation: turning A + B * C into postfix (A B C * +) or prefix (+ A * B C), and calculating the value of such expressions.

  2. Monotonic stacks: a pattern that answers questions like "what is the next greater element?" for every element of an array in O(n) instead of O(n²).

All code in this chapter uses ArrayDeque as the stack, as recommended in the Stack chapter.

Infix, Prefix and Postfix

The way we normally write expressions is called infix, because the operator sits in between its two operands:

A + B

There are two other notations:

Notation

Operator position

A + B

A + B * C

Infix

Between operands

A + B

A + B * C

Prefix (Polish notation)

Before operands

+ A B

+ A * B C

Postfix (Reverse Polish notation)

After operands

A B +

A B C * +

Why bother? Infix is easy for humans but hard for computers. To evaluate A + B * C, you must know that * happens before +, and parentheses can change everything.

Prefix and postfix need no parentheses and no precedence rules. The order of the symbols alone decides the order of the operations. That's why many calculators and expression evaluators first convert infix to postfix and then evaluate the postfix form. A stack does the work in both steps.

Precedence and Associativity

Before converting, we need two rules.

Precedence decides which operator binds tighter:

Operator

Precedence

Associativity

^ (power)

3 (highest)

Right to left

* /

2

Left to right

+ -

1 (lowest)

Left to right

Associativity decides the order when two operators have the same precedence:

A - B - C   means  (A - B) - C      left to right
A ^ B ^ C   means  A ^ (B ^ C)      right to left

For example, 8 - 4 - 2 is (8 - 4) - 2 = 2, not 8 - (4 - 2) = 6. And 2 ^ 3 ^ 2 is 2 ^ 9 = 512, not 8 ^ 2 = 64. Getting associativity wrong is a very common way to lose marks in conversion questions.

Converting Infix to Postfix

The idea: operands go straight to the output. Operators wait on a stack until we know it's their turn.

The Rules

Scan the infix expression from left to right:

  1. Operand (letter or digit): append it to the output.

  2. (: push it.

  3. ): pop operators to the output until you reach (. Pop and discard the (.

  4. Operator op: while the top of the stack is an operator (not () and either

    • it has higher precedence than op, or

    • it has equal precedence and op is left-associative,

    pop it to the output. Then push op.

  5. End of input: pop all remaining operators to the output.

Rule 4 in plain words: before an operator goes on the stack, every operator already there that should be done first gets written out.

Step-by-Step Trace

Convert A + B * C - D / E:

Symbol

Action

Stack (bottom → top)

Output

A

Operand → output

empty

A

+

Stack empty → push

+

A

B

Operand → output

+

A B

*

+ is lower → just push

+ *

A B

C

Operand → output

+ *

A B C

-

Pop * (higher), pop + (equal, left-assoc), push -

-

A B C * +

D

Operand → output

-

A B C * + D

/

- is lower → just push

- /

A B C * + D

E

Operand → output

- /

A B C * + D E

end

Pop everything

empty

A B C * + D E / -

Result: A B C * + D E / -

A Trace with Parentheses and Power

Convert (A + B) * C ^ D ^ E:

Symbol  Stack        Output
(       (
A       (            A
+       ( +          A
B       ( +          A B
)       (empty)      A B +          pop until '(' and discard it
*       *            A B +
C       *            A B + C
^       * ^          A B + C        * is lower than ^, push
D       * ^          A B + C D
^       * ^ ^        A B + C D      equal precedence, but ^ is right-assoc: do NOT pop
E       * ^ ^        A B + C D E
end     (empty)      A B + C D E ^ ^ *

Because ^ is right-associative, the second ^ does not pop the first one. That's how C ^ D ^ E correctly becomes C D E ^ ^, meaning C ^ (D ^ E).

The Quick Exam Method: Full Parenthesization

For short written answers, you can check your result without a stack:

  1. Add brackets around every operation, following precedence and associativity.

  2. For postfix, move each operator to replace its closing bracket. For prefix, move it to replace its opening bracket.

  3. Remove all brackets.

A + B * C - D / E
= ((A + (B * C)) - (D / E))

Postfix: A B C * + D E / -
Prefix:  - + A * B C / D E

In exams, the stack trace table above is usually what earns the marks, so use this method only to double-check.

Converting Infix to Prefix

The standard trick reuses the postfix algorithm:

  1. Reverse the infix expression, and swap every ( with ).

  2. Run the postfix conversion on it, with one change to rule 4: for equal precedence, pop only if the incoming operator is right-associative (^). For + - * /, equal precedence does not pop.

  3. Reverse the result.

Why the change in step 2? Reversing the expression flips the direction of associativity. If we used the normal rule, A - B - C would come out as - A - B C, which means A - (B - C), a different value. With the modified rule we correctly get - - A B C, meaning (A - B) - C.

Trace for A + B * C - D / E. Reversed: E / D - C * B + A.

Symbol  Stack     Output
E                 E
/       /         E
D       /         E D
-       -         E D /        / is higher: pop it, then push -
C       -         E D / C
*       - *       E D / C
B       - *       E D / C B
+       - +       E D / C B *  * is higher: pop it; - is equal, + is left-assoc: keep it
A       - +       E D / C B * A
end               E D / C B * A + -

Reverse: - + A * B C / D E

This matches the answer from full parenthesization.

Evaluating a Postfix Expression

Evaluation is where postfix pays off. The rule is very short. Scan from left to right:

  • Number: push it.

  • Operator: pop two values. The first popped is the right operand, the second popped is the left operand. Compute and push the result.

At the end, the stack holds exactly one value: the answer.

Evaluate 6 2 3 + - 3 8 2 / + *:

Token  Action                 Stack (bottom → top)
6      push                   6
2      push                   6 2
3      push                   6 2 3
+      2 + 3 = 5              6 5
-      6 - 5 = 1              1
3      push                   1 3
8      push                   1 3 8
2      push                   1 3 8 2
/      8 / 2 = 4              1 3 4
+      3 + 4 = 7              1 7
*      1 * 7 = 7              7

Answer: 7

Look at the - step: the stack was 6 5, we popped 5 first (right operand) and 6 second (left operand), so we computed 6 - 5, not 5 - 6. For + and * the order doesn't matter, but for -, / and ^ it does.

In infix, this expression is (6 - (2 + 3)) * (3 + 8 / 2) = 1 * 7 = 7.

Evaluating a Prefix Expression

Prefix evaluation is the mirror image. Scan from right to left, push numbers, and when you see an operator, pop two values. This time the first popped is the left operand.

Evaluate - + 10 * 2 8 3:

Token  Action                 Stack (bottom → top)
3      push                   3
8      push                   3 8
2      push                   3 8 2
*      2 * 8 = 16             3 16
10     push                   3 16 10
+      10 + 16 = 26           3 26
-      26 - 3 = 23            23

Answer: 23

In infix, this is (10 + 2 * 8) - 3 = 23.

Postfix evaluation

Prefix evaluation

Scan direction

Left to right

Right to left

First value popped

Right operand

Left operand

Second value popped

Left operand

Right operand

Time / space

O(n) / O(n)

O(n) / O(n)

Expression Conversion and Evaluation in Java

For conversion, operands are single letters or digits and spaces are not needed. For evaluation, tokens are separated by spaces so that numbers like 10 can have several digits.

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

class Main {

    static int precedence(char op) {
        switch (op) {
            case '+': case '-': return 1;
            case '*': case '/': return 2;
            case '^': return 3;
            default: return -1;     // not an operator
        }
    }

    static boolean isOperator(char c) {
        return precedence(c) > 0;
    }

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

    static String infixToPostfix(String infix) {
        StringBuilder out = new StringBuilder();
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : infix.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                out.append(c);                          // operand: output directly
            } else if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                while (stack.peek() != '(') {
                    out.append(stack.pop());            // pop until '('
                }
                stack.pop();                            // discard '('
            } else if (isOperator(c)) {
                while (!stack.isEmpty() && stack.peek() != '('
                        && (precedence(stack.peek()) > precedence(c)
                            || (precedence(stack.peek()) == precedence(c)
                                && !isRightAssociative(c)))) {
                    out.append(stack.pop());
                }
                stack.push(c);
            }
            // spaces are ignored
        }
        while (!stack.isEmpty()) {
            out.append(stack.pop());
        }
        return out.toString();
    }

    static String infixToPrefix(String infix) {
        // 1. Reverse the expression and swap '(' with ')'
        StringBuilder reversed = new StringBuilder();
        for (int i = infix.length() - 1; i >= 0; i--) {
            char c = infix.charAt(i);
            if (c == '(') {
                reversed.append(')');
            } else if (c == ')') {
                reversed.append('(');
            } else {
                reversed.append(c);
            }
        }

        // 2. Convert to "postfix", popping equal precedence only for '^'
        StringBuilder out = new StringBuilder();
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : reversed.toString().toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                out.append(c);
            } else if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                while (stack.peek() != '(') {
                    out.append(stack.pop());
                }
                stack.pop();
            } else if (isOperator(c)) {
                while (!stack.isEmpty() && stack.peek() != '('
                        && (precedence(stack.peek()) > precedence(c)
                            || (precedence(stack.peek()) == precedence(c)
                                && isRightAssociative(c)))) {
                    out.append(stack.pop());
                }
                stack.push(c);
            }
        }
        while (!stack.isEmpty()) {
            out.append(stack.pop());
        }

        // 3. Reverse the result
        return out.reverse().toString();
    }

    static int apply(char op, int a, int b) {
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/': return a / b;
            case '^': return (int) Math.pow(a, b);
            default: throw new IllegalArgumentException("Unknown operator " + op);
        }
    }

    // Tokens are separated by spaces, so numbers can have many digits
    static int evaluatePostfix(String postfix) {
        Deque<Integer> stack = new ArrayDeque<>();

        for (String token : postfix.trim().split("\\s+")) {
            if (token.length() == 1 && isOperator(token.charAt(0))) {
                int b = stack.pop();        // right operand comes out FIRST
                int a = stack.pop();        // left operand
                stack.push(apply(token.charAt(0), a, b));
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

    static int evaluatePrefix(String prefix) {
        Deque<Integer> stack = new ArrayDeque<>();
        String[] tokens = prefix.trim().split("\\s+");

        for (int i = tokens.length - 1; i >= 0; i--) {   // scan right to left
            String token = tokens[i];
            if (token.length() == 1 && isOperator(token.charAt(0))) {
                int a = stack.pop();        // left operand comes out FIRST
                int b = stack.pop();        // right operand
                stack.push(apply(token.charAt(0), a, b));
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {

        String[] expressions = {
            "A+B*C",
            "A+B*C-D/E",
            "(A+B)*(C-D)",
            "A-B-C",
            "A^B^C",
            "(A+B)*C^D^E",
            "A*(B+C*D)+E"
        };

        for (String e : expressions) {
            System.out.printf("%-14s postfix: %-12s prefix: %s%n",
                    e, infixToPostfix(e), infixToPrefix(e));
        }

        System.out.println(evaluatePostfix("6 2 3 + - 3 8 2 / + *"));
        System.out.println(evaluatePostfix("10 2 8 * + 3 -"));
        System.out.println(evaluatePrefix("- + 10 * 2 8 3"));
        System.out.println(evaluatePrefix("* - 6 2 + 3 / 8 2"));
    }
}

Output:

A+B*C          postfix: ABC*+        prefix: +A*BC
A+B*C-D/E      postfix: ABC*+DE/-    prefix: -+A*BC/DE
(A+B)*(C-D)    postfix: AB+CD-*      prefix: *+AB-CD
A-B-C          postfix: AB-C-        prefix: --ABC
A^B^C          postfix: ABC^^        prefix: ^A^BC
(A+B)*C^D^E    postfix: AB+CDE^^*    prefix: *+AB^C^DE
A*(B+C*D)+E    postfix: ABCD*+*E+    prefix: +*A+B*CDE
7
23
23
28

Notes on this code:

  • The program assumes the input is a valid expression. A production version would check for things like an empty stack before pop() and a missing (.

  • / is integer division in Java, so 7 / 2 gives 3 (it rounds towards zero).

  • Every symbol is pushed and popped at most once, so conversion and evaluation both run in O(n) time with O(n) space for the stack.

Monotonic Stack

Now for a very different use of stacks, one of the most valuable patterns for coding interviews.

Consider this problem:

For every element in an array, find the next greater element: the first element to its right that is larger. If there is none, use -1.

arr    = [4, 5, 2, 10, 8]
answer = [5, 10, 10, -1, -1]

The brute-force solution checks every element to the right of each element, which is O(n²). A monotonic stack solves it in O(n).

A monotonic stack is a stack whose elements are always kept in sorted order (always increasing or always decreasing from bottom to top). Before pushing a new element, we pop every element that would break the order, and those pops are exactly where we find our answers.

The Key Insight

Think of people standing in a line, all looking to the right. A short person's view is blocked by the first taller person. Once someone taller arrives, every shorter person waiting behind them has found their answer, and they will never matter again.

So we keep a stack of elements that are still waiting for a greater element. When a new element arrives, it is the answer for every waiting element smaller than it. We pop those, record the answer, and push the new element.

The waiting elements always form a decreasing stack (from bottom to top), because any smaller element below a bigger one would already have been popped.

Step-by-Step Trace

arr = [4, 5, 2, 10, 8] (the stack stores indexes, shown here by their values):

i=0, value 4:  stack empty, push               stack: [4]
i=1, value 5:  4 < 5 → answer for 4 is 5, pop
               push 5                           stack: [5]
i=2, value 2:  5 < 2? no. push 2                stack: [5, 2]
i=3, value 10: 2 < 10 → answer for 2 is 10, pop
               5 < 10 → answer for 5 is 10, pop
               push 10                          stack: [10]
i=4, value 8:  10 < 8? no. push 8               stack: [10, 8]
End: 10 and 8 never found a greater element → -1

Result: [5, 10, 10, -1, -1]

We store indexes in the stack rather than values, so that we know which position in the result array to fill. Indexes also let us compute distances, as in the daily temperatures problem below.

Why Is It O(n)?

There is a while loop inside a for loop, so it looks like O(n²). But each index is pushed exactly once and popped at most once. Over the whole run, the inner loop can pop at most n times in total. So the total work is at most 2n stack operations:

Time:  O(n)   (amortized O(1) per element)
Space: O(n)   (the stack, in the worst case, e.g. a decreasing array)

This "count the total pushes and pops" argument is the standard way to explain monotonic stack complexity in an interview.

The Four Variations

By changing the comparison and the scan direction, the same pattern answers four related questions:

Question

Stack order (bottom → top)

Pop while

Answer is found

Next greater element

Decreasing

top < current

For each popped element: current

Next smaller element

Increasing

top > current

For each popped element: current

Previous greater element

Decreasing

top <= current

For current: the top after popping

Previous smaller element

Increasing

top >= current

For current: the top after popping

A simple way to remember it: for a "next" question, answers are written when elements are popped. For a "previous" question, the answer is whatever is left on top after popping. Whether you use < or <= decides how equal values are treated, so read the problem statement carefully ("greater" vs "greater or equal").

For example, previous smaller element of [4, 5, 2, 10, 8]:

4:  nothing on the left             → -1     stack: [4]
5:  top 4 < 5, keep it              → 4      stack: [4, 5]
2:  pop 5, pop 4, stack empty       → -1     stack: [2]
10: top 2 < 10                      → 2      stack: [2, 10]
8:  pop 10, top 2 < 8               → 2      stack: [2, 8]

Result: [-1, 4, -1, 2, 2]

Classic Monotonic Stack Problems

Daily Temperatures

Problem: Given daily temperatures, for each day find how many days you must wait for a warmer day (0 if never).

temps  = [73, 74, 75, 71, 69, 72, 76, 73]
answer = [ 1,  1,  4,  2,  1,  1,  0,  0]

This is "next greater element", except the answer is the distance i - day instead of the value. For day 2 (75), the next warmer day is day 6 (76), so the answer is 6 - 2 = 4.

Stock Span

Problem: The span of a stock's price today is the number of consecutive days, ending today, on which the price was less than or equal to today's price.

prices = [100, 80, 60, 70, 60, 75, 85]
span   = [  1,  1,  1,  2,  1,  4,  6]

For day 5 (price 75), going back: 60, 70, 60 are all ≤ 75, then 80 is bigger. So the span is 4 (days 2, 3, 4 and 5).

This is a previous greater element problem: the span is i - (index of previous greater price), or i + 1 if there is no greater price before it.

Largest Rectangle in a Histogram

Problem: Bars of width 1 have the given heights. Find the area of the largest rectangle that fits inside the histogram.

heights = [2, 1, 5, 6, 2, 3]

6 |             ###
5 |         @@@ @@@
4 |         @@@ @@@
3 |         @@@ @@@     ###
2 | ###     @@@ @@@ ### ###
1 | ### ### @@@ @@@ ### ###
  +-------------------------
    2   1   5   6   2   3

@ = largest rectangle: height 5, width 2 (bars 5 and 6) → area 10

For each bar, the biggest rectangle that uses that bar as its shortest bar extends left until the previous smaller bar and right until the next smaller bar. A monotonic increasing stack finds both boundaries at once: when a bar is popped, the current index is its right boundary and the new top of the stack is its left boundary.

width = right - left - 1
area  = height × width

We add an extra height of 0 at the end so that every remaining bar gets popped and measured. Trace of the important pops:

i=4 (height 2) pops height 6: left = index 2, width = 4 - 2 - 1 = 1, area = 6
               pops height 5: left = index 1, width = 4 - 1 - 1 = 2, area = 10  ← best
i=6 (height 0) pops height 3: area 3, height 2: width 4, area 8, height 1: width 6, area 6

Monotonic Stack in Java

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

class Main {

    // For each element, the first greater element to its right (-1 if none)
    static int[] nextGreater(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>();   // indexes, values decreasing

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                result[stack.pop()] = arr[i];    // arr[i] is the answer for the popped index
            }
            stack.push(i);
        }
        return result;
    }

    // For each element, the nearest smaller element to its left (-1 if none)
    static int[] previousSmaller(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();   // values increasing

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && stack.peek() >= arr[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(arr[i]);
        }
        return result;
    }

    // Days to wait for a warmer temperature (0 if never)
    static int[] dailyTemperatures(int[] temps) {
        int n = temps.length;
        int[] wait = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();   // indexes of days still waiting

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
                int day = stack.pop();
                wait[day] = i - day;
            }
            stack.push(i);
        }
        return wait;
    }

    // Stock span: consecutive days up to today with price <= today's price
    static int[] stockSpan(int[] prices) {
        int n = prices.length;
        int[] span = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();   // indexes, prices decreasing

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
                stack.pop();
            }
            span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
            stack.push(i);
        }
        return span;
    }

    // Largest rectangle in a histogram
    static int largestRectangle(int[] heights) {
        int n = heights.length;
        int best = 0;
        Deque<Integer> stack = new ArrayDeque<>();   // indexes, heights increasing

        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];       // height 0 at the end flushes the stack
            while (!stack.isEmpty() && heights[stack.peek()] > h) {
                int height = heights[stack.pop()];
                int left = stack.isEmpty() ? -1 : stack.peek();
                int width = i - left - 1;
                best = Math.max(best, height * width);
            }
            stack.push(i);
        }
        return best;
    }

    public static void main(String[] args) {

        int[] arr = {4, 5, 2, 10, 8};
        System.out.println("Next greater:     " + Arrays.toString(nextGreater(arr)));
        System.out.println("Previous smaller: " + Arrays.toString(previousSmaller(arr)));

        int[] temps = {73, 74, 75, 71, 69, 72, 76, 73};
        System.out.println("Daily temps wait: " + Arrays.toString(dailyTemperatures(temps)));

        int[] prices = {100, 80, 60, 70, 60, 75, 85};
        System.out.println("Stock span:       " + Arrays.toString(stockSpan(prices)));

        int[] heights = {2, 1, 5, 6, 2, 3};
        System.out.println("Largest rectangle: " + largestRectangle(heights));
    }
}

Output:

Next greater:     [5, 10, 10, -1, -1]
Previous smaller: [-1, 4, -1, 2, 2]
Daily temps wait: [1, 1, 4, 2, 1, 1, 0, 0]
Stock span:       [1, 1, 1, 2, 1, 4, 6]
Largest rectangle: 10

All five functions run in O(n) time and O(n) space. In largestRectangle, the loop pushes the extra index n at the end; it is never read, so heights[n] is never accessed.

Complexity Summary

Problem

Brute force

With a stack

Extra space

Infix to postfix / prefix

-

O(n)

O(n)

Evaluate postfix / prefix

-

O(n)

O(n)

Next / previous greater or smaller

O(n²)

O(n)

O(n)

Daily temperatures

O(n²)

O(n)

O(n)

Stock span

O(n²)

O(n)

O(n)

Largest rectangle in histogram

O(n²)

O(n)

O(n)

Common Mistakes

1. Popping operands in the wrong order

In postfix evaluation, the first value popped is the right operand. Writing a = pop(); b = pop(); push(a - b) computes 5 - 6 instead of 6 - 5. In prefix evaluation it is the other way round.

2. Treating ^ as left-associative

A ^ B ^ C is A B C ^ ^ in postfix, not A B ^ C ^. When the incoming operator is ^ and the top is also ^, do not pop.

3. Pushing ) onto the stack, or forgetting to discard (

Closing brackets are never pushed, and brackets never appear in postfix or prefix output.

4. Forgetting to empty the stack at the end

After the scan, operators may still be waiting on the stack. Pop all of them to the output.

5. Simply reversing the postfix to get prefix

Reversing A B C * + gives + * C B A, which is wrong (the operands are reversed too). Use the reverse, convert, reverse method, or full parenthesization.

6. Storing values when you need indexes

In monotonic stack problems that ask for distances or positions (daily temperatures, histogram), push indexes. You can always get the value with arr[index], but not the other way round.

7. Mixing up < and <= with duplicates

"Next greater" uses top < current to pop; using <= would treat an equal value as "greater". Test your code with an array that has repeated values, like [2, 2, 3].

Interview Tips

  • Recognise the monotonic stack pattern from words like "next greater", "next smaller", "previous", "nearest", "span", "how many days until", "how far can it see", or "largest rectangle".

  • Explain the O(n) argument clearly: every index is pushed once and popped at most once.

  • State what the stack contains before coding: "a decreasing stack of indexes still waiting for a greater element". Saying this out loud makes the comparisons obvious.

  • For circular arrays (Next Greater Element II), loop i from 0 to 2n - 1 and use i % n, pushing indexes only during the first pass.

  • For calculator problems (evaluate a string like "3 + 2 * 2"), you can either convert to postfix and evaluate, or use two stacks at once, one for numbers and one for operators, applying the same precedence rules.

  • In exam conversion questions, always draw the full table with columns for symbol, stack and output, and write the final answer separately.

Practice Problems

  1. Evaluate Reverse Polish Notation

  2. Basic Calculator II

  3. Next Greater Element I

  4. Next Greater Element II (circular array)

  5. Daily Temperatures

  6. Online Stock Span

  7. Remove K Digits

  8. Largest Rectangle in Histogram (hard)

  9. Trapping Rain Water (hard, can be solved with a monotonic stack)

The Main Idea

Stacks are the natural tool whenever the most recent unfinished item must be handled first.

Infix → Postfix:   operands to output, operators wait on a stack
                   pop higher (or equal, if left-assoc) before pushing
Evaluate postfix:  push numbers; on an operator pop right, then left, push result
Evaluate prefix:   scan right to left; pop left, then right
Monotonic stack:   keep the stack sorted; every pop answers a question
                   each element pushed once, popped once → O(n)

For expressions, a stack holds operators until their turn comes. For "next greater" style questions, a monotonic stack holds elements until their answer arrives. In both cases, each element enters and leaves the stack once, which is why these solutions are linear.