Why Arithmetic Expressions Need a Stack
A stack's Last-In-First-Out (LIFO) discipline mirrors exactly how nested operations must be "undone" in the reverse order they were opened — which is exactly what evaluating a mathematical expression requires.
The Core Applications of Stack in Expression Handling OVERVIEW
• Parenthesis / bracket matching — push an opening bracket, pop and match on a closing one; mismatch or leftover items signal invalid syntax.
• Infix → Postfix / Prefix conversion — a stack holds operators until their correct position (by precedence & associativity) is determined.
• Postfix / Prefix expression evaluation — a stack holds intermediate operands; operators pop their operands, compute, and push the result back.
• Function call & recursion management — the call stack itself is the same LIFO structure, one level more abstract.
Why Not Just Evaluate Infix Directly? THE PROBLEM
Infix expressions like 3 + 4 × 2 require the reader to already know operator precedence and associativity, and to scan back and forth to resolve parentheses — awkward for a machine reading left to right in one pass. Postfix (and prefix) notation removes ambiguity entirely: no parentheses and no precedence rules are needed to evaluate them, because the order of operators already encodes the order of operations.
📌 This is precisely why compilers translate infix source code into postfix-like intermediate representations before generating machine code.
Balanced Parentheses Check — The Simplest Stack Application WARM-UP
// Given a string of ( ) [ ] { }, is it balanced?
for each character c in expression:
if c is an opening bracket:
push(c)
else if c is a closing bracket:
if stack is empty or pop() doesn't match c:
return "unbalanced"
return stack.isEmpty() ? "balanced" : "unbalanced"
Infix, Prefix & Postfix Notation
The same expression can be written three ways depending on where the operator sits relative to its two operands.
Definitions TERMINOLOGY
| Notation | Operator Position | Example (A+B) |
| Infix | Between the two operands | A + B |
| Prefix (Polish) | Before both operands | + A B |
| Postfix (Reverse Polish) | After both operands | A B + |
📌 "Polish notation" is named after logician Jan Łukasiewicz (Polish), who introduced prefix notation in the 1920s. "Reverse Polish Notation" (RPN) — postfix — later became the input method for HP scientific calculators.
Worked Example — A Longer Expression STEP BY STEP
Consider the infix expression: (A + B) × (C − D)
Infix: (A + B) × (C − D)
Postfix: A B + C D − ×
Prefix: × + A B − C D
Reading postfix left to right: "A B +" means (A+B); then "C D −" means (C−D); finally "×" multiplies those two results — exactly the original expression's meaning, with zero parentheses required.
Operator Precedence & Associativity RULES USED BY CONVERSION
| Operator | Precedence | Associativity |
| ( ) | highest | — |
| ^ (power) | 3 | Right → Left |
| × , / | 2 | Left → Right |
| + , − | 1 (lowest) | Left → Right |
Infix → Postfix Conversion (Shunting-Yard Style)
Edsger Dijkstra's classic algorithm: scan left to right, use a stack to hold operators until precedence tells you it's safe to output them.
Algorithm PSEUDOCODE
for each token in infix expression (left to right):
if token is an operand (letter/digit):
append token to output
else if token == '(':
push(token)
else if token == ')':
while top of stack != '(':
append pop() to output
pop() // discard the '('
else // token is an operator
while stack not empty and top != '(' and
( prec(top) > prec(token) or
( prec(top) == prec(token) and token is left-associative ) ):
append pop() to output
push(token)
while stack not empty:
append pop() to output
Worked Example — Step by Step A + B × (C − D)
Converting A + B * (C - D) to postfix, one token at a time:
| Step | Token | Action | Stack (top→right) | Output so far |
| 1 | A | operand → output | A | |
| 2 | + | stack empty → push | + | A |
| 3 | B | operand → output | + | A B |
| 4 | * | prec(*) > prec(+) → push | + * | A B |
| 5 | ( | push | + * ( | A B |
| 6 | C | operand → output | + * ( | A B C |
| 7 | − | top is '(' → push | + * ( − | A B C |
| 8 | D | operand → output | + * ( − | A B C D |
| 9 | ) | pop until '(' → pop −, discard ( | + * | A B C D − |
| 10 | end | pop all remaining | (empty) | A B C D − * + |
✓ Final Postfix: A B C D − * + — try this same expression in the Animated Visualizer tab to watch it happen live.
Infix → Prefix Conversion
Prefix conversion reuses the postfix algorithm with a clever trick: reverse the input, swap brackets, convert to "postfix," then reverse the result.
Algorithm — The Reverse-Twice Trick PSEUDOCODE
function infixToPrefix(infix):
1. reverse(infix)
2. swap every '(' with ')' and vice versa
3. postfix = infixToPostfix(step-2 result)
// same algorithm as before, but use prec(top) >= prec(token)
// for right-associativity when scanning the reversed string
4. reverse(postfix)
return step-4 result
Worked Example — Step by Step A + B × (C − D)
| Stage | Result |
| Original infix | A + B * ( C − D ) |
| 1. Reverse the string | ) D − C ( * B + A |
| 2. Swap ( ↔ ) | ( D − C ) * B + A |
| 3. Convert to postfix | D C − B * A + |
| 4. Reverse the postfix result | + A * B − C D |
✓ Final Prefix: + A * B − C D — reading left to right: "+" needs (A) and (* B − C D); "*" needs (B) and (−C D); "−" needs (C) and (D). Same expression, unambiguous, no parentheses.
Why Not Just Run the Postfix Algorithm on the Original String? SUBTLETY
Because prefix operators must precede their operands, but the natural left-to-right scan of the postfix algorithm only knows how to place an operator after it has already seen both operands. Reversing the string turns "operator comes first" into "operator comes last" — exactly what the postfix algorithm already knows how to build — and reversing back restores the original left-to-right operator-first order.
Evaluating a Postfix Expression
This is the payoff: once an expression is in postfix form, evaluation needs only a single left-to-right scan and a stack of operands — no precedence rules, no parentheses.
Algorithm PSEUDOCODE
for each token in postfix expression (left to right):
if token is an operand (number):
push(token)
else // token is an operator
b = pop() // second operand (popped first!)
a = pop() // first operand
result = apply(token, a, b) // e.g. a + b, a - b, a * b
push(result)
return pop() // the single remaining value is the answer
⚠️ Operand order matters for non-commutative operators (−, /): the first popped value is the right-hand operand, the second popped value is the left-hand operand — i.e. compute (a op b), not (b op a).
Worked Example — Step by Step 2 3 4 * + 5 −
Evaluate the postfix expression 2 3 4 * + 5 - (equivalent infix: 2 + 3×4 − 5):
| Token | Action | Stack (bottom→top) |
| 2 | push 2 | [2] |
| 3 | push 3 | [2, 3] |
| 4 | push 4 | [2, 3, 4] |
| * | pop 4, pop 3 → 3*4=12 → push | [2, 12] |
| + | pop 12, pop 2 → 2+12=14 → push | [14] |
| 5 | push 5 | [14, 5] |
| − | pop 5, pop 14 → 14−5=9 → push | [9] ✓ final answer |
✓ Result = 9, matching 2 + 3×4 − 5 = 2 + 12 − 5 = 9.
Evaluating Prefix — Scan Right to Left MIRROR IMAGE
Prefix expressions are evaluated the same way, but the scan runs right to left (since the operator appears before its operands, you need to see the operands first):
for each token in prefix expression (right to left):
if operand: push(token)
else:
a = pop() // first operand (left-hand)
b = pop() // second operand (right-hand)
push(apply(token, a, b))
return pop()
Animated Visualizer — Watch the Stack Work
Pick a mode, enter an expression, and step through the exact algorithm token by token — with adjustable playback speed and full pause/resume control.
Setup CONFIGURE
📌 Use single-letter operands (A–Z) and operators + − * / ^ with ( ). Example:
A+B*(C-D)Playback LIVE
TOKEN STREAM — CURRENT TOKEN HIGHLIGHTED
STACK (top at bottom of column)
OUTPUT / RESULT BUILDING
STEP EXPLANATION
STEP LOG
C Implementation
A complete, self-contained C program: array-based stack, infix-to-postfix conversion, and postfix evaluation.
stack.h — Array-Based Stack HEADER
#define MAX 100
typedef struct {
char data[MAX];
int top;
} Stack;
void initStack(Stack *s) { s->top = -1; }
int isEmpty(Stack *s) { return s->top == -1; }
int isFull(Stack *s) { return s->top == MAX - 1; }
void push(Stack *s, char c) {
if (isFull(s)) { printf("Stack overflow\n"); return; }
s->data[++(s->top)] = c;
}
char pop(Stack *s) {
if (isEmpty(s)) { printf("Stack underflow\n"); return '\0'; }
return s->data[(s->top)--];
}
char peek(Stack *s) {
return isEmpty(s) ? '\0' : s->data[s->top];
}
infix_to_postfix.c CONVERSION
int precedence(char op) {
if (op == '^') return 3;
if (op == '*' || op == '/') return 2;
if (op == '+' || op == '-') return 1;
return 0;
}
int isRightAssoc(char op) { return op == '^'; }
void infixToPostfix(char *infix, char *postfix) {
Stack s; initStack(&s);
int j = 0;
for (int i = 0; infix[i] != '\0'; i++) {
char c = infix[i];
if (isalnum(c)) {
postfix[j++] = c; // operand -> output
} else if (c == '(') {
push(&s, c);
} else if (c == ')') {
while (!isEmpty(&s) && peek(&s) != '(')
postfix[j++] = pop(&s);
pop(&s); // discard '('
} else { // operator
while (!isEmpty(&s) && peek(&s) != '(' &&
(precedence(peek(&s)) > precedence(c) ||
(precedence(peek(&s)) == precedence(c) && !isRightAssoc(c))))
postfix[j++] = pop(&s);
push(&s, c);
}
}
while (!isEmpty(&s)) postfix[j++] = pop(&s);
postfix[j] = '\0';
}
evaluate_postfix.c EVALUATION
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;
}
int evaluatePostfix(char *postfix) {
int stk[MAX], top = -1;
for (int i = 0; postfix[i] != '\0'; i++) {
char c = postfix[i];
if (isdigit(c)) {
stk[++top] = c - '0'; // operand -> push
} else {
int b = stk[top--]; // popped first = right operand
int a = stk[top--]; // popped second = left operand
stk[++top] = applyOp(a, b, c);
}
}
return stk[top]; // final result
}
int main() {
char infix[] = "A+B*(C-D)";
char postfix[MAX];
infixToPostfix(infix, postfix);
printf("Postfix: %s\n", postfix);
char expr[] = "234*+5-";
printf("Result: %d\n", evaluatePostfix(expr)); // prints 9
return 0;
}
📌 Both functions share the exact same Stack ADT from stack.h — the same underlying data structure that powers parenthesis matching, function call stacks, and undo/redo history.