Self-checkedTier 1 27 min readpds.stack-applications

Stack applications: expression evaluation and matching

What a stack is used for. Convert infix to postfix with an operator stack (precedence, associativity, parentheses), evaluate postfix and prefix, build an expression tree, check brackets, find the next greater element and the stock span with a monotonic stack, and keep a running minimum. Includes the counting facts (balanced strings and valid postfix strings are Catalan) and the traps with operand order and stack depth.

Why it exists

A stack serves the most recent unfinished thing first. That is exactly the shape of anything nested: a parenthesis that has been opened but not yet closed, an operator whose right operand has not yet arrived, a function call that has not yet returned. So the stack is the standard tool for reading and evaluating expressions, for checking that brackets match, and for problems of the form "look back to the nearest earlier item that is bigger". GATE asks these as hand-execution questions (convert, evaluate, find the largest stack size) and as counting questions, so the exact rules matter.

Prerequisites

Stack (abstract data type)

Precise definitions

Three notations for a binary operation. Infix: the operator is between the operands (A + B). Prefix or Polish: before them (+ A B). Postfix or reverse Polish: after them (A B +). Infix needs precedence, associativity and parentheses to be unambiguous. For binary operators of fixed arity, prefix and postfix need none of them: the order of the symbols alone fixes the evaluation, and they contain no parentheses. (A unary minus needs its own symbol, otherwise - is ambiguous.)
Precedence and associativity used on this page (the usual exam convention; the question states its own if it differs):

Operator	Precedence	Associativity
`^` (power)	highest	right: `A^B^C = A^(B^C)`
`*` `/`	middle	left: `A/BC = (A/B)C`
`+` `-`	lowest	left: `A-B-C = (A-B)-C`

(C itself has no power operator; ^ in C is bitwise exclusive or. Questions that use ^ for power say so.)

Infix to postfix with a stack. Scan the infix string left to right with an operator stack and an output string.
1. Operand: append to the output.
2. (: push.
3. ): pop operators to the output until a ( is on top, then discard that (.
4. Operator $\theta$ : while the top of the stack is an operator (not () with higher precedence than $\theta$ , or equal precedence when $\theta$ is left associative, pop it to the output. Then push $\theta$ .
5. At the end pop everything left to the output.
A ( on the stack is never popped by an operator; it only leaves when its ) arrives.
Evaluate postfix. Scan left to right with a value stack. An operand is pushed. An operator pops two values: the first one popped is the right operand $b$ , the second is the left operand $a$ ; push $a \,\theta\, b$ . At the end the stack holds exactly one value, the result. A string is a valid postfix expression iff no operator ever finds fewer than two values and the end leaves exactly one; it then has one more operand than operators.
Evaluate prefix. Scan right to left; an operand is pushed; an operator pops two values, and now the first popped is the left operand.
Expression tree. The postfix string is the postorder of the expression tree, the prefix string is its preorder, and the inorder with parentheses added is the infix form. To build the tree from postfix, use a stack of node pointers: an operand pushes a leaf; an operator pops the right subtree, then the left subtree, and pushes a new node that has them as children.
Relation between prefix and postfix. The reverse of the postfix string of a tree is the prefix string of the mirrored tree (left and right children exchanged). It is not the prefix string of the same tree. It equals it only if the tree is identical to its own mirror image (for example A-A); making the operators commutative does not help, because the strings differ even when the values do not.
Balanced brackets. Push every opening bracket; a closing bracket must match the top, which is then popped; at the end the stack must be empty. For one kind of bracket this equals "the running count of unclosed brackets never goes below 0 and ends at 0".
Counting. The number of balanced strings with $n$ pairs of one kind of bracket is the Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$ ( $1, 2, 5, 14, 42, 132, \ldots$ for $n = 1, 2, \ldots$ ). With $k$ kinds of brackets it is $k^n C_n$ . The number of valid postfix strings made of $n$ operand symbols and $n - 1$ binary operator symbols (the number of different binary expression-tree shapes) is $C_{n-1}$ .
Monotonic stack: next greater element. For each position, find the nearest position to the right with a larger value. Scan left to right with a stack of positions whose answer is still unknown (their values never increase from bottom to top, and strictly decrease when all values are different). A new value pops and answers every smaller value on the top, then is pushed. Every position is pushed once and popped at most once, so the total time is $O(n)$ , although there is a loop inside a loop.
Stock span (a variant): the span of day $i$ is the number of consecutive days up to and including $i$ with a price not above day $i$ 's; the stack holds the days with a strictly higher price than any later day, and the span is $i$ minus the position of the top after popping (or $i + 1$ if the stack is empty).
Minimum in constant time. Keep, next to every stack entry, the minimum of the stack up to that entry (or a second stack that is pushed whenever a new minimum appears). Push, pop and min are all $O(1)$ .
Other uses. The call stack of recursion; explicit-stack versions of recursive algorithms (iterative inorder, depth-first search); undo and the back button of a browser; reversing a sequence.
Cost. All the scans above are $O(n)$ for an input of length $n$ , with an auxiliary stack of up to $O(n)$ entries.

How it works

Infix to postfix

Step through the conversion of A+B*(C^D-E). Notice what makes an operator wait on the stack (its right operand has not been read yet), what makes it leave (a later operator that must be done first, or a closing parenthesis), and that the final pops flush the rest.

Infix to postfix with an operator stack

Real run

C source

1#include <ctype.h>

2#include <stdio.h>

4static int prec(char c) {

5 switch (c) {

6 case '^': return 3;

7 case '*':

8 case '/': return 2;

9 case '+':

10 case '-': return 1;

11 default: return 0;

12 }

13}

15void to_postfix(const char *in, char *out) {

16 char st[64];

17 int top = 0, k = 0;

18 for (int i = 0; in[i]; i++) {

19 char c = in[i];

20 if (isalnum((unsigned char)c)) {

21 out[k++] = c;

22 } else if (c == '(') {

23 st[top++] = c;

24 } else if (c == ')') {

25 while (top > 0 && st[top - 1] != '(') {

26 out[k++] = st[--top];

27 }

28 top--; /* discard the ( */

29 } else {

30 while (top > 0 && st[top - 1] != '(' &&

31 (prec(st[top - 1]) > prec(c) || (prec(st[top - 1]) == prec(c) && c != '^'))) {

32 out[k++] = st[--top];

33 }

34 st[top++] = c;

35 }

36 }

37 while (top > 0) {

38 out[k++] = st[--top];

39 }

40 out[k] = '\0';

41}

Input, left to right

(

)

Operator stack

bottomempty

Output (postfix)

empty

Blue = the position this step is working on, amber = a position being compared, red = positions just swapped, green = finished or in its final place, a filled blue cell = a value just placed, faded = not part of the structure at this step.

Step 1

Convert A+B*(C^D-E). Read one character at a time; operands go to the output, operators wait on the stack.

1 / 17

The input A+B*(C^D-E) is passed to to_postfix() by hidden driver code. Single letters are operands, ^ is right associative. to_postfix() and prec() are the exact code that runs. Produced by: real execution: every array, stack, matrix and list in the picture is read from the running program's memory at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog

Evaluating postfix

The input 82/3-42*+ is read once. Watch the order of the two pops: for - the first pop is the right operand (3) and the second is the left operand (4), so the result is $4 - 3 = 1$ , not $3 - 4$ .

Evaluating a postfix expression with a value stack

Real run

C source

1#include <stdio.h>

3int eval_postfix(const char *s) {

4 int st[64], top = 0;

5 for (int i = 0; s[i]; i++) {

6 char c = s[i];

7 if (c >= '0' && c <= '9') {

8 st[top++] = c - '0';

9 } else {

10 int b = st[--top];

11 int a = st[--top];

12 int v = 0;

13 switch (c) {

14 case '+': v = a + b; break;

15 case '-': v = a - b; break;

16 case '*': v = a * b; break;

17 case '/': v = a / b; break;

18 }

19 st[top++] = v;

20 }

21 }

22 return st[0];

23}

Postfix input, left to right

Value stack

bottomempty

Step 1

Evaluate 82/3-42*+. Operands are pushed; an operator pops two values and pushes the result.

1 / 11

The input 82/3-42*+ (single digits) is passed to eval_postfix() by hidden driver code. eval_postfix() is the exact code that runs. Note that the second popped value is the LEFT operand. Produced by: real execution: every array, stack, matrix and list in the picture is read from the running program's memory at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog

Checking brackets

Three inputs run through the same function: a balanced one, one where the closing bracket does not match the most recent opener, and one that ends with an opener left on the stack.

Checking brackets with a stack: three inputs

Real run

C source

1#include <stdio.h>

3int balanced(const char *s) {

4 char st[64];

5 int top = 0;

6 for (int i = 0; s[i]; i++) {

7 char c = s[i];

8 if (c == '(' || c == '[' || c == '{') {

9 st[top++] = c;

10 } else if (c == ')' || c == ']' || c == '}') {

11 if (top == 0) {

12 return 0;

13 }

14 char o = st[--top];

15 if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{')) {

16 return 0;

17 }

18 }

19 }

20 return top == 0;

21}

Input

{

[

(

)

]

}

Stack of open brackets

bottomempty

Step 1

Check the string {[()]}.

1 / 20

Three strings are passed to balanced() by hidden driver code: {[()]} (balanced), ([)] (wrong order) and (() (an opener is left over). balanced() is the exact code that runs. Produced by: real execution: every array, stack, matrix and list in the picture is read from the running program's memory at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog

Monotonic stack: next greater element

The stack holds positions that are still waiting for a greater value to their right. A big value arrives and answers everything smaller on the top.

Next greater element with a stack of indices

Real run

C source

1#include <stdio.h>

3void next_greater(const int *a, int n, int *ans) {

4 int st[64], top = 0;

5 for (int i = 0; i < n; i++) {

6 while (top > 0 && a[st[top - 1]] < a[i]) {

7 ans[st[--top]] = a[i];

8 }

9 st[top++] = i;

10 }

11 while (top > 0) {

12 ans[st[--top]] = -1;

13 }

14}

Input array a

Answers so far (blank = not known yet)

Stack of positions (bottom to top)

bottomempty

Step 1

Find, for every position, the first greater value to its right.

1 / 16

The array 4, 5, 2, 25, 7, 8, 1 is set up by hidden driver code. next_greater() is the exact code that runs. The stack holds positions whose answer is not yet known; their values are decreasing from bottom to top. Produced by: real execution: every array, stack, matrix and list in the picture is read from the running program's memory at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog

Worked examples

EX 1Converting infix to postfix, and how deep the stack gets

Easy

#include <ctype.h>
#include <stdio.h>
#include <string.h>
 
static int prec(char c) {
    switch (c) {
    case '^': return 3;
    case '*':
    case '/': return 2;
    case '+':
    case '-': return 1;
    default: return 0;
    }
}
 
/* returns the largest number of symbols the operator stack held */
static int to_postfix(const char *in, char *out) {
    char st[64];
    int top = 0, k = 0, deepest = 0;
    for (int i = 0; in[i]; i++) {
        char c = in[i];
        if (isalnum((unsigned char)c)) {
            out[k++] = c;
        } else if (c == '(') {
            st[top++] = c;
        } else if (c == ')') {
            while (top > 0 && st[top - 1] != '(')
                out[k++] = st[--top];
            top--;
        } else {
            while (top > 0 && st[top - 1] != '(' &&
                   (prec(st[top - 1]) > prec(c) || (prec(st[top - 1]) == prec(c) && c != '^')))
                out[k++] = st[--top];
            st[top++] = c;
        }
        if (top > deepest) deepest = top;
    }
    while (top > 0)
        out[k++] = st[--top];
    out[k] = '\0';
    return deepest;
}
 
int main(void) {
    const char *tests[] = {"A+B*C", "A*B+C", "A+B*C-D/E", "(A+B)*(C-D)", "A^B^C", "A-B-C", "A/B*C", "((A+B)*(C+D))", "A*(B+(C*(D+E)))"};
    char out[64];
    printf("%-18s %-14s %s\n", "infix", "postfix", "stack depth");
    for (int t = 0; t < 9; t++) {
        int d = to_postfix(tests[t], out);
        printf("%-18s %-14s %d\n", tests[t], out, d);
    }
    return 0;
}

Output:

infix              postfix        stack depth
A+B*C              ABC*+          2
A*B+C              AB*C+          1
A+B*C-D/E          ABC*+DE/-      2
(A+B)*(C-D)        AB+CD-*        3
A^B^C              ABC^^          2
A-B-C              AB-C-          1
A/B*C              AB/C*          1
((A+B)*(C+D))      AB+CD+*        4
A*(B+(C*(D+E)))    ABCDE+*+*      7

Reading it. Each line is one run of the conversion on the same function as the animation. Some things to read off:

A+B*C gives ABC*+: the + waits because * binds tighter and so must act first. A*B+C gives AB*C+: the * is popped as soon as the + arrives.
A-B-C gives AB-C- (left associative: equal precedence pops the earlier one), but A^B^C gives ABC^^ (right associative: the equal-precedence ^ waits).
A/B*C gives AB/C*: / and * have the same precedence and are left associative, so the division is done first.
Stack depth counts every symbol on the stack, including (. ((A+B)*(C+D)) reaches 4 (two parentheses, the * and the + under the second parenthesis); A*(B+(C*(D+E))) reaches 7 because every operator and every parenthesis is still waiting when E is read.

EX 2Evaluating postfix and prefix; how much stack is needed

Easy

#include <stdio.h>
#include <string.h>
 
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;
    default: return 0;
    }
}
 
/* postfix: scan left to right; the FIRST value popped is the RIGHT operand */
static int eval_postfix(const char *s, int *deepest) {
    int st[64], top = 0;
    *deepest = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            st[top++] = s[i] - '0';
        } else {
            int b = st[--top];
            int a = st[--top];
            st[top++] = apply(s[i], a, b);
        }
        if (top > *deepest) *deepest = top;
    }
    return st[0];
}
 
/* prefix: scan right to left; the FIRST value popped is the LEFT operand */
static int eval_prefix(const char *s) {
    int st[64], top = 0;
    for (int i = (int)strlen(s) - 1; i >= 0; i--) {
        if (s[i] >= '0' && s[i] <= '9') {
            st[top++] = s[i] - '0';
        } else {
            int a = st[--top];
            int b = st[--top];
            st[top++] = apply(s[i], a, b);
        }
    }
    return st[0];
}
 
int main(void) {
    const char *post[] = {"82/3-42*+", "53+82-*"};
    int d;
    for (int t = 0; t < 2; t++) {
        int v = eval_postfix(post[t], &d);
        printf("postfix %-10s = %3d (stack never held more than %d values)\n", post[t], v, d);
    }
    eval_postfix("12+3+4+", &d);
    printf("postfix 12+3+4+    needs a stack of depth %d\n", d);
    eval_postfix("1234+++", &d);
    printf("postfix 1234+++    needs a stack of depth %d\n", d);
    printf("prefix  %-10s = %3d\n", "+*23-82", eval_prefix("+*23-82"));
    printf("prefix  %-10s = %3d\n", "-/84*23", eval_prefix("-/84*23"));
    return 0;
}

Output:

postfix 82/3-42*+  =   9 (stack never held more than 3 values)
postfix 53+82-*    =  48 (stack never held more than 3 values)
postfix 12+3+4+    needs a stack of depth 2
postfix 1234+++    needs a stack of depth 4
prefix  +*23-82    =  12
prefix  -/84*23    =  -4

Reading it. 82/3-42*+ is $8/2 - 3 + 4 \cdot 2 = 4 - 3 + 8 = 9$ ; the first operator / pops 2 first (the right operand) and 8 second. 53+82-* is $(5 + 3) \cdot (8 - 2) = 48$ . The prefix strings are scanned from the right, and the first value popped is the left operand: +*23-82 is $2 \cdot 3 + (8 - 2) = 12$ and -/84*23 is $8/4 - 2 \cdot 3 = -4$ . The last two lines show that the stack size needed to evaluate a postfix string depends on its shape, not just on the number of operands: 12+3+4+ (left-leaning, $((1 + 2) + 3) + 4$ ) needs only 2, and 1234+++ (right-leaning, $1 + (2 + (3 + 4))$ ) needs 4, the number of operands.

EX 3From postfix to the expression tree and the other two forms

Medium

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    char sym;
    struct node *left, *right;
};
 
static struct node *mk(char sym, struct node *l, struct node *r) {
    struct node *n = malloc(sizeof *n);
    if (n == NULL) exit(1);
    n->sym = sym;
    n->left = l;
    n->right = r;
    return n;
}
 
/* operands become leaves; an operator pops the right subtree first, then the left one */
static struct node *from_postfix(const char *s, int *deepest) {
    struct node *st[64];
    int top = 0;
    *deepest = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            st[top++] = mk(s[i], NULL, NULL);
        } else {
            struct node *r = st[--top];
            struct node *l = st[--top];
            st[top++] = mk(s[i], l, r);
        }
        if (top > *deepest) *deepest = top;
    }
    return st[0];
}
 
static void pre(const struct node *t) {
    if (t == NULL) return;
    printf("%c", t->sym);
    pre(t->left);
    pre(t->right);
}
 
static void in(const struct node *t) {
    if (t == NULL) return;
    if (t->left) printf("(");
    in(t->left);
    printf("%c", t->sym);
    in(t->right);
    if (t->right) printf(")");
}
 
static void post(const struct node *t) {
    if (t == NULL) return;
    post(t->left);
    post(t->right);
    printf("%c", t->sym);
}
 
static void destroy(struct node *t) {
    if (t == NULL) return;
    destroy(t->left);
    destroy(t->right);
    free(t);
}
 
int main(void) {
    int d;
    struct node *root = from_postfix("ABC*+D-", &d);
    printf("prefix : ");
    pre(root);
    printf("\ninfix  : ");
    in(root);
    printf("\npostfix: ");
    post(root);
    printf("\nroot is %c; the node stack held at most %d nodes\n", root->sym, d);
    destroy(root);
    return 0;
}

Output:

prefix : -+A*BCD
infix  : ((A+(B*C))-D)
postfix: ABC*+D-
root is -; the node stack held at most 3 nodes

Reading it. The postfix string ABC*+D- is read with a stack of nodes. A, B, C become three leaves; * takes C as the right child and B as the left child and pushes the node B*C; + combines A and B*C; D becomes a leaf; - combines A+(B*C) and D. The root is -. The preorder is the prefix form -+A*BCD, the inorder with parentheses is the infix form ((A+(B*C))-D) (the parentheses can be dropped where precedence makes them redundant, giving A+B*C-D), and the postorder gives back the original postfix string. The node stack held at most 3 nodes (the three leaves before the first operator). A prefix string is turned into a tree the same way, scanning from the right; there an operator pops its left subtree first, then its right (the reverse of the postfix case).

EX 4Counting balanced strings and valid postfix strings

GATE level

#include <stdio.h>
 
static int balanced(const char *s, int len, int kinds) {
    char st[32];
    int top = 0;
    const char *open = "([{", *close = ")]}";
    for (int i = 0; i < len; i++) {
        int is_open = 0;
        for (int k = 0; k < kinds; k++) {
            if (s[i] == open[k]) {
                st[top++] = (char)k;
                is_open = 1;
            }
        }
        if (is_open) continue;
        if (top == 0) return 0;
        int k = st[--top];
        if (s[i] != close[k]) return 0;
    }
    return top == 0;
}
 
/* counts the strings of length 2n over the opening and closing symbols of the given number of kinds that are balanced */
static long count_balanced(int n, int kinds) {
    const char *symbols = "()[]{}";
    int len = 2 * n, alphabet = 2 * kinds;
    long total = 0, strings = 1;
    for (int i = 0; i < len; i++) strings *= alphabet;
    for (long code = 0; code < strings; code++) {
        char s[16];
        long c = code;
        for (int i = 0; i < len; i++) {
            int sym = (int)(c % alphabet);
            c /= alphabet;
            s[i] = symbols[sym];
        }
        total += balanced(s, len, kinds);
    }
    return total;
}
 
/* valid postfix strings with n operand symbols a and n - 1 operator symbols o */
static long count_postfix(int n) {
    int len = 2 * n - 1;
    long total = 0;
    for (long mask = 0; mask < (1L << len); mask++) {
        int ones = 0;
        for (int i = 0; i < len; i++) ones += (int)((mask >> i) & 1);
        if (ones != n) continue;
        int depth = 0, ok = 1;
        for (int i = 0; i < len && ok; i++) {
            if ((mask >> i) & 1) {
                depth++;
            } else {
                if (depth < 2) ok = 0;
                depth--;
            }
        }
        if (ok && depth == 1) total++;
    }
    return total;
}
 
int main(void) {
    printf("n: balanced strings with n pairs (1 kind of bracket), (3 kinds), valid postfix strings with n + 1 operands\n");
    for (int n = 1; n <= 6; n++) {
        long three = n <= 4 ? count_balanced(n, 3) : -1;
        long pf = count_postfix(n + 1);
        if (three >= 0) printf("%d: %ld, %ld, %ld\n", n, count_balanced(n, 1), three, pf);
        else printf("%d: %ld, -, %ld\n", n, count_balanced(n, 1), pf);
    }
    return 0;
}

Output:

n: balanced strings with n pairs (1 kind of bracket), (3 kinds), valid postfix strings with n + 1 operands
1: 1, 3, 1
2: 2, 18, 2
3: 5, 135, 5
4: 14, 1134, 14
5: 42, -, 42
6: 132, -, 132

Reading it. The program tries every string of the given length and counts. Balanced strings of $n$ pairs of one bracket kind are $1, 2, 5, 14, 42, 132$ , the Catalan numbers $C_n$ . With three bracket kinds they are $3, 18, 135, 1134$ , which is $3^n C_n$ : shape (the Catalan number) times a free choice of kind for every pair. The third column counts strings of $n + 1$ operand symbols and $n$ operator symbols that are valid postfix expressions, and again gives $C_n$ . That is because a valid postfix string is the postorder of one binary tree shape, and the number of full binary tree shapes with $n + 1$ leaves ( $n$ operators) is $C_n$ . Deleting the leaves gives the ordinary binary trees with $n$ nodes, which is the count on the counting page. (The program treats every operand as the same symbol and every operator as the same symbol, so it counts patterns, not expressions with different variables.)

EX 5Stock span with a monotonic stack

Medium

#include <stdio.h>
 
int main(void) {
    int price[7] = {100, 80, 60, 70, 60, 75, 85};
    int span[7], st[7], top = 0, pushes = 0, pops = 0;
    for (int i = 0; i < 7; i++) {
        while (top > 0 && price[st[top - 1]] <= price[i]) {
            top--;
            pops++;
        }
        span[i] = top == 0 ? i + 1 : i - st[top - 1];
        st[top++] = i;
        pushes++;
    }
    printf("price:");
    for (int i = 0; i < 7; i++) printf(" %3d", price[i]);
    printf("\nspan: ");
    for (int i = 0; i < 7; i++) printf(" %3d", span[i]);
    printf("\n%d pushes and %d pops for %d prices\n", pushes, pops, 7);
    return 0;
}

Output:

price: 100  80  60  70  60  75  85
span:    1   1   1   2   1   4   6
7 pushes and 5 pops for 7 prices

Reading it. The span of a day is how many consecutive days up to and including it had a price not above it. Day 3 (70) has span 2 because day 2 (60) is not above it and day 1 (80) is; day 6 (85) has span 6: days 1 to 6 are all at most 85 and day 0 (100) stops the run. After the pops only day 0 is left on the stack, so the span is $6 - 0 = 6$ . The counts at the end show why the loop-in-a-loop is linear: 7 pushes and 5 pops for 7 prices. Each day is pushed once and popped at most once.

EX 6A stack that knows its minimum

Medium

#include <stdio.h>
 
static int data[32], mins[32], n;
 
static void push(int x) {
    data[n] = x;
    mins[n] = (n == 0 || x < mins[n - 1]) ? x : mins[n - 1];
    n++;
}
 
static int pop(void) { return data[--n]; }
 
int main(void) {
    int ops[9] = {5, 3, 7, 3, 8, -1, -1, -1, -1}; /* a negative number means pop */
    for (int i = 0; i < 9; i++) {
        if (ops[i] >= 0) {
            push(ops[i]);
            printf("push %d: ", ops[i]);
        } else {
            printf("pop %d: ", pop());
        }
        if (n > 0) printf("minimum is %d (stack size %d)\n", mins[n - 1], n);
        else printf("stack is empty\n");
    }
    return 0;
}

Output:

push 5: minimum is 5 (stack size 1)
push 3: minimum is 3 (stack size 2)
push 7: minimum is 3 (stack size 3)
push 3: minimum is 3 (stack size 4)
push 8: minimum is 3 (stack size 5)
pop 8: minimum is 3 (stack size 4)
pop 3: minimum is 3 (stack size 3)
pop 7: minimum is 3 (stack size 2)
pop 3: minimum is 5 (stack size 1)

Reading it. Every stack position stores, next to the value, the minimum of everything at or below it, so min is just the top's stored minimum and popping needs no search. After push 3 the minimum is 3 and stays 3 when 7, a second 3 and 8 arrive. When the second 3 is popped the minimum is still 3 (the first 3 is below), and only when the first 3 is popped does it return to 5. All three operations take $O(1)$ time, at the price of one extra integer per entry.

EX 7A long conversion by hand, step by step

GATE level

Convert K+L-M*N+(O^P)*W/U/V*T+Q to postfix. The table is the output of the same algorithm.

Symbol	Action	Stack after	Output after
`K`	operand: output	(empty)	`K`
`+`	push	`+`	`K`
`L`	operand: output	`+`	`KL`
`-`	pop +, push	`-`	`KL+`
`M`	operand: output	`-`	`KL+M`
`*`	push	`-*`	`KL+M`
`N`	operand: output	`-*`	`KL+MN`
`+`	pop *, pop -, push	`+`	`KL+MN*-`
`(`	push	`+(`	`KL+MN*-`
`O`	operand: output	`+(`	`KL+MN*-O`
`^`	push	`+(^`	`KL+MN*-O`
`P`	operand: output	`+(^`	`KL+MN*-OP`
`)`	pop ^, discard (	`+`	`KL+MN*-OP^`
`*`	push	`+*`	`KL+MN*-OP^`
`W`	operand: output	`+*`	`KL+MN*-OP^W`
`/`	pop *, push	`+/`	`KL+MN-OP^W`
`U`	operand: output	`+/`	`KL+MN-OP^WU`
`/`	pop /, push	`+/`	`KL+MN-OP^WU/`
`V`	operand: output	`+/`	`KL+MN-OP^WU/V`
`*`	pop /, push	`+*`	`KL+MN-OP^WU/V/`
`T`	operand: output	`+*`	`KL+MN-OP^WU/V/T`
`+`	pop *, pop +, push	`+`	`KL+MN-OP^WU/V/T*+`
`Q`	operand: output	`+`	`KL+MN-OP^WU/V/T*+Q`
end	pop +	(empty)	`KL+MN-OP^WU/V/T*+Q+`

Reading it. The answer is KL+MN*-OP^W*U/V/T*+Q+. The stack never holds more than 3 symbols (+, (, ^ at the deepest). The steps to watch are the equal-precedence ties: the + after N pops both the * (higher precedence) and the - (equal precedence, left associative), while the second / pops the first / because of the tie. The table was generated by a script that follows exactly the rules above, and the C function of the first example returns the same final string for this input.

EX 8Which strings are valid postfix expressions?

GATE level

Which of AB+C*, AB+*C, ABC+*D and AB*CD*+ are valid postfix expressions with binary operators?

Run the stack count for each: an operand adds 1 to the count of values on the stack and a binary operator needs the count to be at least 2 and then subtracts 1. The string is valid iff the count never fails and ends at 1.

String	Counts after each symbol	Valid?
`AB+C*`	1, 2, 1, 2, 1	yes: $(A + B) \cdot C$
`AB+*C`	1, 2, 1, then `*` needs 2 values but only 1	no
`ABC+*D`	1, 2, 3, 2, 1, 2	no: ends with 2 values (4 operands, 2 operators)
`ABCD+`	1, 2, 1, 2, 3, 2, 1	yes: $A B \cdot C D$ joined by $+$

Reading it. A quick necessary test is "operands = operators + 1". It rules out the third string, but it is not sufficient: AB+*C has three operands and two operators and is still invalid. So run the count. This is also why the number of valid postfix strings with $n + 1$ operands is the Catalan number $C_n$ .

Cheat box

Infix $\to$ postfix: operand $\to$ output; ( push; ) pop to (; operator pops higher (or equal, for left-associative) precedence, then pushes; end: pop all. ^ is right associative.
Postfix evaluation: left to right; operator pops $b$ first then $a$ ; push $a \,\theta\, b$ . Prefix: right to left; first pop is the left operand.
Postfix = postorder, prefix = preorder, parenthesised infix = inorder of the expression tree. Reverse of postfix = prefix of the mirrored tree.
Valid postfix: operands = operators + 1 and never fewer than 2 values before an operator.
Balanced strings: $C_n$ for $n$ pairs, $k^n C_n$ for $k$ kinds. Valid postfix with $n + 1$ operands: $C_n$ .
Monotonic stack: next greater element and stock span in $O(n)$ (each element pushed once, popped once).
Min-stack: store the running minimum with each entry; all operations $O(1)$ .
Stack size: operator stack counts ( too; postfix evaluation depth depends on the shape (between 2 and the number of operands, when there are at least 2 operands).

Traps and GATE patterns

Connections

Builds on

Stack (abstract data type)

Unlocks

Stack (abstract data type)uses

Across subjects

No cross-subject links yet.

Within this subject

Stack (abstract data type)uses Binary tree traversalsuses Counting binary treesuses Recursion and the call stackanalogous-to

Queue applications and queue using stackscontrasts-withplanned

All of this is the stack ADT at work. The expression tree ties it to tree traversals: postfix is postorder and prefix is preorder. The number of valid postfix strings is the Catalan count of the counting page. The operator stack plays the role the call stack plays for recursion: the thing started most recently finishes first.

PYQs

2 previous year questions from your book. I re-solved each one myself (2 by running or simulating, 0 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2015 · Set 3 · MCQ · 1 markQ6 · page 62 of the book

The result evaluating the postfix expression
10 5+60 6/*8-is

(a)248
(b)213
(c)142
(d)71

GATE 2007 · MCQ · 2 marksQ11 · page 63 of the book

The following postfix expression with single digit
operands is evaluated using a stack:
8 2 3 ^ / 2 3 * + 5 1 * -
Note that is the exponentiation operator. The top
two elements of the stack after the first * is
evaluated are:

(a)6,1
(b)5,7
(c)3,2
(d)1,5

Self-check

Question 1

Convert a*(b+c)-d/e to postfix.

Show answer

abc+*de/-. The + is inside the parentheses, so it is popped by the ); then * is popped by the - (higher precedence), the - waits, / is pushed over it (higher precedence), and the two are popped at the end in the order / then -.

Question 2

Evaluate the postfix expression 5 1 2 + 4 * + 3 - (single-digit operands).

Show answer

Stack: 5; 5 1; 5 1 2; + gives 5 3; 5 3 4; * gives 5 12; + gives 17; 17 3; - gives $17 - 3 = 14$ .

Question 3

Is AB+*C a valid postfix expression? Is AB+C* ?

Show answer

AB+*C is not valid: the * finds only one value on the stack (the result of AB+). AB+C* is valid: it is $(A + B) \cdot C$ .

Question 4

How many different balanced strings are there with 3 pairs of brackets of two kinds, round and square?

Show answer

$2^3 \cdot C_3 = 8 \cdot 5 = 40$ : five bracket shapes, and each of the three pairs can be round or square independently.

Question 5

Give the next greater element to the right for 3 1 4 2 5 (use $-1$ for none).

Show answer

4 4 5 5 -1. With the stack: 3 is pushed; 1 is pushed; 4 pops 1 and 3 (both answered by 4) and is pushed; 2 is pushed; 5 pops 2 and 4 and is pushed; at the end 5 is left with no answer.

Revision card

One-screen revision

Infix $\to$ postfix: operands out; ( push; ) pop to (; operator pops higher or equal precedence (equal only if left associative; ^ is right); end: pop all.
Postfix evaluation: first pop = right operand. Prefix: scan right to left, first pop = left operand.
Postfix = postorder, prefix = preorder of the expression tree; reverse of postfix = prefix of the mirror.
Valid postfix: operands = operators + 1, never fewer than two values before an operator; count $C_n$ for $n + 1$ operands.
Brackets: push openers, match and pop closers; empty at the end. $C_n$ for one kind, $k^n C_n$ for $k$ kinds.
Monotonic stack: next greater, span in $O(n)$ . Min-stack: store the running minimum with each entry.
The operator stack counts (; postfix evaluation depth depends on the shape.

References

·Horowitz, Sahni, Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Chapter 3 Stacks and Queues (evaluation of expressions)
·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., Section 10.1 Stacks and queues (the stack operations)

Verification

The four animations replay real runs of the shown to_postfix(), eval_postfix(), balanced() and next_greater() functions: the input, the stacks and the output are read from the running program, and the test suite checks the final results, the largest stack sizes, that the output of the conversion grows by at most one symbol per step and that the stack in next_greater is decreasing from bottom to top. All C programs on this page are compiled with -Wall -Wextra -Werror and run by npm run verify:c. The facts below were checked by scripts/enum-checks/stacks.py: the conversion against Python's own evaluation of 9973 random expressions (with + - * / and ^, parentheses and ties), that the number of valid postfix strings with n operands is the Catalan number C(n-1) for n up to 8, that the number of balanced strings is C(n) for one kind of bracket and 3^n C(n) for three kinds, that building a tree from postfix or prefix gives back the tree, that the reverse of a postfix string is the prefix string of the MIRRORED tree, and the next greater element against brute force. The textbook chapter and section numbers were written from memory and have NOT been checked against the books. CLRS 10.1 only covers the stack operations; the conversion algorithm, the monotonic stack, the counting facts and the min-stack are standard material that is derived and checked here rather than taken from those sources. The treatment of the exponent operator as right associative is the usual convention of exam questions and must be taken from the question. The prose and the GATE-pattern claims have NOT yet had a human textbook check (the independent second pass is described at the end of these notes). SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand (long C programs were not re-read line by line: they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Priority queues and building a heap

Graph representations