Stack Application

DSA, Database System & Operating System — Data Structure, Lists, Linked Lists and Trees, NEC licence examination syllabus (Nepal Engineering Council).

Stack Application: Infix to Postfix, the exam classic

The single most repeated numerical involving stacks in this entire subject.

Humans naturally write infix (A+B), but computers evaluate expressions faster using postfix (AB+) — no parentheses, no precedence rules needed, just read left to right.

Worked example — convert A+B*C to postfix using a stack: Scan left to right, use operator-precedence stack: A → output: A + → push + stack: [+] B → output: A B * → * has higher precedence than +, push * stack: [+,*] C → output: A B C end → pop remaining operators: *, then + Final postfix: A B C * +

Worked example — evaluate postfix "5 3 4 * +" using a stack: 5 → push 5 stack: [5] 3 → push 3 stack: [5,3] 4 → push 4 stack: [5,3,4] * → pop 4,3 → 3*4=12, push 12 stack: [5,12] + → pop 12,5 → 5+12=17, push 17 stack: [17] Final result: 17

💡 Practice both directions (infix→postfix conversion, AND evaluating a postfix expression) on at least 3 different expressions each, including ones with parentheses — this exact pair of numericals appears almost every year.

The case with parentheses, where the rules actually bite

A+B*C is settled by precedence alone. Parentheses are where the algorithm needs its two special rules, and where marks are lost.

Convert (A+B)*C-D to postfix: read output stack why ───────────────────────────────────────────────────────── ( — ( push an opening bracket A A ( operands go straight to output + A ( + stack top is '(', so nothing pops B A B ( + ) A B + — pop until '(' , then DISCARD the '(' * A B + * stack empty, push C A B + C * - A B + C * - '-' is lower than '*', so pop '*' first D A B + C * D - end A B + C * D - pop what remains Postfix: A B + C * D −

🔑 The two rules about brackets

'(' is pushed, never comparedOnce on the stack it blocks all popping — nothing above it is removed until its ')' arrives. That is what makes the bracket override precedence.

Brackets never reach the outputPop operators until '(' is found, then discard both brackets. Postfix needs no brackets, which is the entire point of converting.

💡 More conversions to check yourself against: A+B*C → ABC*+ · (A+B)*C → AB+C* · A+B*C−D/E → ABC*+DE/− · A*(B+C)/D → ABC+*D/. Note the first two use identical symbols in the same order and give different answers — that difference is exactly what the brackets do.

Evaluating postfix, and why it needs no precedence at all

Evaluation is the simpler direction and follows one rule: operand → push; operator → pop two, apply, push the result.

Evaluate 5 3 4 * + : read 5 → push stack: [5] read 3 → push stack: [5, 3] read 4 → push stack: [5, 3, 4] read * → pop 4 and 3, compute 3*4 = 12, push stack: [5, 12] read + → pop 12 and 5, compute 5+12 = 17, push stack: [17] Answer: 17 — one value left on the stack, as there must be.

Note the order when popping: the first value popped is the RIGHT operand. It makes no difference for + and *, but for − and / it decides the answer entirely. Evaluating 5 3 − means 5 − 3 = 2, not 3 − 5.

💡 A finished evaluation leaves exactly one value on the stack. More than one means the expression had too many operands; running out mid-way means too few operators. That check catches most arithmetic slips before they cost marks.

Syllabus points

Infix to postfix conversion
Evaluation of postfix expression

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.