Noesis
3.2.6Linear Data Structures

Stack applications — balanced parentheses, infix-to-postfix, function call stack

2,013 words9 min readdifficulty · medium
🇮🇳 Yeh note Hinglish mein padho →

1. Balanced Parentheses

HOW (algorithm):

  1. For each char:
    • If it is an opener ( [ { → push it.
    • If it is a closer → if stack empty → fail; else pop and check it matches.
  2. At end, stack must be empty (no unfulfilled promises).

2. Infix → Postfix (Shunting-Yard idea)

HOW (algorithm): scan left→right, keep an operator stack, build output:

  • Operand → append to output.
  • ( → push.
  • ) → pop to output until (; discard the (.
  • Operator o → while stack top is an operator with higher precedence, or equal precedence and o is left-associative → pop it to output. Then push o.
  • End → pop everything to output.
Figure — Stack applications — balanced parentheses, infix-to-postfix, function call stack

3. The Function Call Stack

Recall Feynman: explain to a 12-year-old

Imagine a stack of plates. You can only add or take from the top. Brackets are like opening boxes: the box you opened last is the one you must close first — so you stack each opened box and pop it when you close it. For sums, the stack lets a "weak" plus-sign wait while a "strong" times-sign jumps ahead. And when one task calls a helper task, the first task waits on the stack until the helper finishes — last started, first finished.

Flashcards

Which property of a stack makes it perfect for nested structures?
LIFO — the most recently opened item must be closed/resolved first.
In balanced-parentheses, what two conditions mean success?
Every closer matched the popped opener AND the stack is empty at the end.
Why does counting equal ( and ) fail?
It ignores order/nesting, e.g. )( and ([)] pass the count but are unbalanced.
In infix→postfix, what do you do on an operand?
Append it directly to the output.
In infix→postfix, what do you do on )?
Pop operators to output until (, then discard the (.
When operator o arrives, when do you pop the stack top?
While top is an operator of higher precedence, or equal precedence with o left-associative.
Convert a + b * c to postfix.
a b c * +
Convert (a + b) * c to postfix.
a b + c *
Why is ^ treated specially?
It's right-associative, so you do NOT pop an equal-precedence ^.
What does a function stack frame store?
Return address, parameters, local variables, saved registers.
Why does the call that started last return first?
A caller is paused until its callee returns — pure LIFO unwinding.
What causes a stack overflow in recursion?
Too many un-returned frames (e.g., missing/late base case) exhaust stack memory.

Connections

  • Stack — ADT and Implementation (the LIFO operations used here)
  • Recursion and the Call Stack
  • Expression Trees and Evaluation
  • Postfix Evaluation Algorithm
  • Queues (contrast: FIFO vs LIFO)
  • Operator Precedence and Associativity

Concept Map

models

applies to

applies to

applies to

opener

closer

valid needs

catches crossing

uses

driven by

produces

orders

LIFO stack
last in first out

Nested matched
structure

Balanced parentheses

Infix to postfix

Function call stack

Push opener

Pop and match

Stack empty at end

Operator precedence

Operator stack waits

Postfix RPN output

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, stack ka ek hi superpower hai: LIFO — jo cheez sabse last me andar gayi, wahi sabse pehle bahar aati hai. Aur duniya ke bahut saare problems "nested" hote hain — yaani jo last me khula, wahi pehle band hona chahiye. Isiliye stack inke liye perfect tool hai.

Balanced parentheses: har opening bracket ( [ { ko stack me push karo. Jab koi closing bracket aaye, to top ko pop karke check karo ki match ho raha hai ya nahi. Aakhir me agar stack empty hai to string balanced hai. Sirf count barabar dekhna galat hai, kyunki )( me count to barabar hai par order galat hai — order matter karta hai, isiliye stack chahiye.

Infix to postfix: humare normal expressions (a + b * c) me precedence aur brackets ka dimaag lagana padta hai. Postfix (a b c * +) me yeh tension khatam — machine ek hi stack se left-to-right evaluate kar leti hai. Operand ko seedha output me daalo, operators ko stack me rakho. Jab naya operator aaye aur stack ka top zyada (ya barabar + left-associative) precedence ka ho, to use pehle nikaalo. ) aaye to ( tak sab nikaal do. Yeh stack ka kaam hai chhote operator ko wait karwana jab tak bada operator pehle nahi ho jaata.

Function call stack: jab f ne g ko call kiya, f ruk jaata hai aur g ke return hone ka wait karta hai. Last me call hua function pehle return hota hai — pure LIFO. Har call ka ek "frame" banta hai jisme return address, parameters, local variables hote hain. Recursion me agar base case nahi hai ya bahut deep chala gaya, to frames bhar jaate hain aur stack overflow ho jaata hai. Isliye recursion ka depth dhyaan rakho!

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 1,993 wordsD2Visual walkthroughThe derivation in pictures · 2,339 wordsD3Worked examplesEvery scenario covered · 3,110 wordsD4ExercisesGraded, full solutions · 3,240 wordsD5Question bankConcept traps, quick reveals · 1,716 words

Test yourself — Linear Data Structures

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

Operator precedence — full tableCoding · 5.1.5