Bytebook Compiler

Stacks & Queues

Stack Applications

Balanced brackets, infix to postfix conversion and postfix evaluation — the three stack algorithms every CSE 102 exam asks you to trace.

6 min read3 runnable examples4-question quiz

1. Balanced brackets

Every opening bracket must be closed by the matching bracket in the right order. Push each opener; on each closer, pop and check it matches.

C
#include <stdio.h>

int isBalanced(const char *s) {
    char st[100];
    int top = -1;
    for (int i = 0; s[i]; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') st[++top] = c;
        else if (c == ')' || c == ']' || c == '}') {
            if (top == -1) return 0;                       // closer with nothing open
            char o = st[top--];
            if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{')) return 0;
        }
    }
    return top == -1;                                      // anything left open?
}

int main(void) {
    const char *tests[] = {"{[a+b]*(c-d)}", "([)]", "((x)", "a[i] = (b + c) * {d}"};
    for (int i = 0; i < 4; i++)
        printf("%-22s %s\n", tests[i], isBalanced(tests[i]) ? "balanced" : "NOT balanced");
    return 0;
}
Output
{[a+b]*(c-d)}          balanced
([)]                   NOT balanced
((x)                   NOT balanced
a[i] = (b + c) * {d}   balanced
Try it Yourself

Infix, prefix and postfix

Notation Operator position A + B * C Needs brackets?
Infix between operands A + B * C yes, plus precedence rules
Prefix (Polish) before operands + A * B C no
Postfix (Reverse Polish) after operands A B C * + no

Computers prefer postfix: it can be evaluated left to right with one stack and no precedence rules.

2. Infix to postfix (shunting-yard)

Scan the infix expression left to right:

  1. Operand → write it to the output.
  2. ( → push it.
  3. ) → pop to the output until the matching (; discard both brackets.
  4. Operator → while the stack top is an operator of higher precedence, or equal precedence and left-associative, pop it to the output. Then push the new operator.
  5. At the end, pop everything left to the output.

Precedence: ^ (highest, right-associative) > * / > + -.

C
#include <stdio.h>
#include <ctype.h>

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

void toPostfix(const char *in, char *out) {
    char st[100];
    int top = -1, k = 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] != '(') out[k++] = st[top--];
            top--;                                            // discard '('
        } else if (prec(c)) {
            while (top >= 0 && st[top] != '(' &&
                   (prec(st[top]) > prec(c) || (prec(st[top]) == prec(c) && c != '^')))
                out[k++] = st[top--];
            st[++top] = c;
        }
    }
    while (top >= 0) out[k++] = st[top--];
    out[k] = '\0';
}

int main(void) {
    const char *exprs[] = {"A+B*C", "(A+B)*C", "A+B*C-D/E", "A*(B+C)/D", "A^B^C", "(A-B/C)*(A/K-L)"};
    char post[100];
    for (int i = 0; i < 6; i++) {
        toPostfix(exprs[i], post);
        printf("%-18s ->  %s\n", exprs[i], post);
    }
    return 0;
}
Output
A+B*C              ->  ABC*+
(A+B)*C            ->  AB+C*
A+B*C-D/E          ->  ABC*+DE/-
A*(B+C)/D          ->  ABC+*D/
A^B^C              ->  ABC^^
(A-B/C)*(A/K-L)    ->  ABC/-AK/L-*
Try it Yourself

Tracing A+B*C-D/E

Symbol Action Stack Output
A output A
+ push + A
B output + AB
* higher than +, push + * AB
C output + * ABC
- pop * and + (≥ precedence), push - - ABC*+
D output - ABC*+D
/ higher than -, push - / ABC*+D
E output - / ABC*+DE
end pop all ABC*+DE/-

3. Evaluating postfix

Scan left to right. Push numbers. On an operator, pop two values — the first pop is the right operand — apply the operator and push the result.

C
#include <stdio.h>
#include <ctype.h>

int evalPostfix(const char *s) {
    int st[100], top = -1;
    for (int i = 0; s[i]; i++) {
        char c = s[i];
        if (c == ' ') continue;
        if (isdigit((unsigned char)c)) {
            int num = 0;
            while (isdigit((unsigned char)s[i])) num = num * 10 + (s[i++] - '0');
            i--;
            st[++top] = num;
        } else {
            int b = st[top--], a = st[top--];       // b is popped first: the right operand
            switch (c) {
                case '+': st[++top] = a + b; break;
                case '-': st[++top] = a - b; break;
                case '*': st[++top] = a * b; break;
                case '/': st[++top] = a / b; break;
            }
        }
    }
    return st[top];
}

int main(void) {
    printf("2 3 1 * + 9 -  = %d\n", evalPostfix("2 3 1 * + 9 -"));
    printf("6 2 / 3 -      = %d\n", evalPostfix("6 2 / 3 -"));
    printf("10 2 8 * + 3 - = %d\n", evalPostfix("10 2 8 * + 3 -"));
    return 0;
}
Output
2 3 1 * + 9 -  = -4
6 2 / 3 -      = 0
10 2 8 * + 3 - = 23
Try it Yourself

Trace of 2 3 1 * + 9 -: push 2, 3, 1 → * pops 1 and 3, pushes 3 → + pops 3 and 2, pushes 5 → push 9 → - pops 9 and 5, pushes 5 − 9 = −4.

Prefix evaluation

Prefix works the same way but scanning right to left, and the first value popped is the left operand. Example: - + 2 * 3 1 9 evaluates to (2 + 3 × 1) − 9 = −4.

Test yourself

4 questions · pick an answer to check it instantly

  1. 1

    What is the postfix form of (A + B) * (C - D)?

  2. 2

    Evaluate the postfix expression 5 1 2 + 4 * + 3 -.

  3. 3

    Which string is not balanced?

  4. 4

    Why is postfix easier for a computer to evaluate than infix?

Esc
↑↓ move↵ open