Stack for Parsing & Nesting (Decode String, Basic Calculator)
Decode String (LC 394)(opens leetcode.com)
You get a string s written in a compact code: k[text] means text written out k times in a row, and text may itself contain more codes, so brackets can sit inside brackets. Expand every code and return the resulting plain string.
Every input keeps a few promises: s is always a correctly formed code, with no stray spaces and a ] for every [; each k is a positive whole number; and digits only ever appear as repeat counts, so the decoded text has no digits of its own (you will never see something like 3a or 2[4]). The inputs are also chosen so that the decoded string is at most 105 characters long.
3[a] gives aaa and 2[bc] gives bcbc; written one after the other they make aaabcbc.Nesting Stack
nested input ➔ push the outer context on open ➔ pop and combine on close| 1 | def decode_string(s: str) -> str: |
| 2 | """Decode String: save the outer text and count at each '[', restore them at ']'. |
| 3 | Time: O(N * L) | Space: O(N + L) |
| 4 | """ |
| 5 | stack: list[tuple[str, int]] = [] # One saved (cur, num) per '[' still open |
| 6 | cur = "" # Text of the innermost open bracket, built so far |
| 7 | num = 0 # Repeat count being read, digit by digit |
| 8 | |
| 9 | for ch in s: |
| 10 | if ch.isdigit(): |
| 11 | # 1. Build The Repeat Count Digit By Digit: |
| 12 | # A count can have several digits, as in "12[a]", so each new digit shifts the earlier |
| 13 | # ones left by one place. |
| 14 | num = num * 10 + int(ch) |
| 15 | elif ch == "[": |
| 16 | # 2. Opener: Save The Outer State, Then Start The Inner One Empty: |
| 17 | # The outer text waits on stack with the count this bracket will use; resetting cur and num |
| 18 | # keeps the inner text from starting with the outer text already in it. |
| 19 | stack.append((cur, num)) |
| 20 | cur, num = "", 0 |
| 21 | elif ch == "]": |
| 22 | # 3. Closer: Restore The Outer State And Fold The Finished Inner Result In: |
| 23 | # The ']' closes the most recent '[', whose saved pair sits on top of stack; the inner text |
| 24 | # goes back after the outer text, repeated k times. |
| 25 | prev, k = stack.pop() |
| 26 | cur = prev + cur * k |
| 27 | else: |
| 28 | # 4. Plain Content Extends The Current Text: |
| 29 | # A letter belongs to whichever bracket is open right now. |
| 30 | cur += ch |
| 31 | |
| 32 | return cur |
stack holds one saved (cur, num) for every [ still open, innermost on top, and cur is the text of the innermost open bracket read so far.A [ starts a smaller problem inside the current one, and the outer text has to wait until that inner problem is finished: so at [ push the outer state (cur, num) onto stack and start the inner text empty, and at ] pop it back and fold the finished inner text in with cur = prev + cur * k. Brackets close in the reverse order they open, so the ] you meet always closes the most recent [ still open, and the top of stack is exactly what that [ saved; everything below it waits untouched for its own ]. That is the whole model for any nesting (brackets, parentheses, folders): last opened, first finished, one saved context per open level. The trap is the reset: stack.append((cur, num)) must be followed by cur, num = "", 0. Keep the old cur and the outer text is repeated inside the bracket ("3[a2[c]]" turns into "aacacaacacaacac"); keep the old num and the next count's digits are glued onto it (the inner 2 is read as 32).
See it run
Decode String, step by step
cur ""num 0stack empty
The top row is s. The bottom row is stack, filled from column 0, with the bottom on the left. Each saved pair is written as cur|num, and a dash means an empty text.
readthe character of s that the loop is readingdigita digit that is added to the count in numsavedthe pair (cur, num) that was just pushed onto stackpopthe saved pair that a closing bracket takes off stack
Start: s = "2[a10[b]]", cur = "", num = 0, and stack is empty.
Gotcha 1 of 5
- The trap
Gotcha 1: Keeping the old
curafter the pushMistakenum = 0Fixcur, num = "", 0What happens: At
[, the outer text is saved onstackwithstack.append((cur, num)). The inner text must then start empty. Ifcurkeeps the outer text, that text is also repeated inside the bracket. At], the outer text is added once more fromstack.Example: s = "3[a2[c]]"Mistake: returns 'aacacaacacaacac'Fix: returns 'accaccacc'
- Nothing opens or closes; each item only waits for the first later item that beats it, as in Daily Temperatures (LC 739). The stack then holds waiting items in sorted order and pops them when a bigger one arrives, instead of saving an outer context at an opener. See Next Greater Element
Deep Dive
Why the top of stack is the bracket that ] closes
A stack gives last in, first out order. Brackets close in the reverse order they open. So when the loop reads a ], the bracket it closes is the most recent [ that is still open. The top of stack is the pair that this [ saved.
At [, the loop pushes (cur, num). cur is the text built so far outside the new bracket. num is the repeat count that belongs to this bracket. The pair waits on stack while the inner text is built. Everything below it waits too, and nothing below it changes.
At ], the loop pops (prev, k) and sets cur = prev + cur * k. The inner text cur is finished, so it is repeated k times and added after the outer text prev. Then cur is the text of the bracket one level up.
Example: in Decode String (LC 394), s = "3[a2[c]]" decodes to "accaccacc". The inner 2[c] becomes "cc". The outer text "a" is put in front, which gives "acc". The outer count 3 repeats it, which gives "accaccacc". stack holds one pair after the first [, two pairs after the second [, and is empty again after the last ].
One trace: a two-digit count and the reset after the push
The board replays s = "2[a10[b]]". The top row is s. The bottom row is stack. A saved pair is written as cur|num, and a dash means an empty text.
The digits 1 and 0 build the count one digit at a time. num = num * 10 + int(ch) gives 1 and then 10. This step is marked as a trap on the board. With num = int(ch), the count would be 0.
At the second [, the loop pushes ("a", 10). The next step resets cur and num to "" and 0. This is the other trap on the board. Without the reset, cur would still be "a" inside the bracket, and num would still be 10.
The first ] pops ("a", 10) and sets cur = "a" + "b" * 10, which is 11 letters. The last ] pops ("", 2) and repeats those 11 letters two times. The answer has 22 letters.
What breaks when a reset or an order is wrong
Each wrong version below changes one line of decode_string. Each one gives a wrong answer without raising an error.
Keep cur after the push. For "3[a2[c]]", the inner text starts with the outer "a". The result is "aacacaacacaacac" and not "accaccacc".
Keep num after the push. For "1[2[a]]", the inner count 2 is added after the old 1 and is read as 12. The result is 12 letters a and not "aa".
Read the count with num = int(ch). For "10[a]", num becomes 1 and then 0, so the result is the empty string and not 10 letters a.
Read stack[-1] and do not pop it. The pair stays on stack, and the next ] uses the same pair again.
Write cur = cur * k + prev. The inner text is placed before the outer text. For "a2[c]", the result is "cca" and not "acc".
The cost, and other problems with the same stack
Let N be the length of s and L the length of the decoded text. The loop reads each character once. Each ] builds a new string of at most L letters, and there are at most N of them. So the time is O(N * L). stack holds at most one pair per open bracket, and cur holds at most L letters, so the space is O(N + L).
The decoded text can be much longer than s. The input "9[9[9[a]]]" has 10 characters and decodes to 729 letters.
Basic Calculator (LC 224) saves the running result and the sign at ( and restores them at ), with the same reset after the push. Simplify Path (LC 71) keeps a stack of folder names, and .. pops one. Valid Parentheses (LC 20) is the smallest case: it pushes the open bracket and pops it when the matching closing bracket arrives.
60-Second Pitch
"The input nests, so I use a stack. A [ starts a smaller problem inside the current one. I push the outer text and its count (cur, num) and start the inner text empty. A ] always closes the most recent [, so the top of the stack is exactly the pair that bracket saved. I pop it and set cur = prev + cur * k. I read counts as num * 10 + digit, and I reset cur and num after every push. The time is O(N * L) and the space is O(N + L), where L is the length of the decoded text."
Common Questions
- Why does a stack fit nested input?
Closing marks match the most recent opening mark that is still open. That is last in, first out order. The top of
stackis always the saved state of the bracket that the next]closes.- Why do you reset
curandnumafter the push? The outer text and count are already saved on
stack. The inner bracket must start with an empty text and no count. Ifcuris kept, the outer text is repeated inside the bracket. Ifnumis kept, the next count's digits are added to it.- How do you read a count such as 12?
Use
num = num * 10 + int(ch)for each digit. After1,numis 1. After2,numis 12. Settingnum = int(ch)keeps only the last digit.- What are the time and space complexity?
O(N * L) time and O(N + L) space, where
Nis the length ofsandLis the length of the decoded text. Each]builds a string of at mostLletters, andstackholds at most one pair per open bracket.- Could you solve it with recursion instead?
Yes. A recursive function can parse one bracket and return its text, and the call stack plays the role of
stack. The iterative version avoids deep recursion on a very deeply nested input, and it makes the saved state(cur, num)visible.
SWE Reasoning
Spot it
- The input nests: brackets inside brackets, parentheses inside parentheses, or folders inside folders.
- An inner part must be finished before the part around it can continue.
- The outer part has a state that must come back after the inner part ends, such as the text built so far and a repeat count.
- Closing marks match the most recent opening mark, so the order is last opened, first finished.
- A recursive solution would work, but it would use the call stack, and a long nested input could overflow it.
The invariant, step by step
stackstarts empty.curis the text of the innermost open bracket, andnumis the count being read.- A digit makes
num = num * 10 + int(ch), so a count with several digits is read correctly. - At
[, the loop pushes(cur, num)and then setscur, num = "", 0. Nowcuris the text of the new innermost bracket. - A letter is added to
cur, because it belongs to the bracket that is open now. - At
], the loop pops(prev, k)and setscur = prev + cur * k. The inner bracket is finished and merged into the outer one. - When the loop ends,
stackis empty andcurholds the whole decoded text.
Traps
- No reset of
curafter the push. The outer text is repeated inside the bracket."3[a2[c]]"gives"aacacaacacaacac". - No reset of
numafter the push. The next count is glued onto the old one."1[2[a]]"reads 12. - One digit at a time.
num = int(ch)loses the earlier digits of a count such as10. - Peek and not pop at
]. The saved pair is used by two brackets. - Wrong fold order.
cur * k + prevputs the inner text before the outer text. Useprev + cur * k. - Saving only one value. The pair must hold both
curandnum. If only one of them is saved, the outer bracket cannot be restored.
Practice
Stack for Parsing & Nesting (Decode String, Basic Calculator)
Decode String (LC 394)(opens leetcode.com)
You get a string s written in a compact code: k[text] means text written out k times in a row, and text may itself contain more codes, so brackets can sit inside brackets. Expand every code and return the resulting plain string.
Every input keeps a few promises: s is always a correctly formed code, with no stray spaces and a ] for every [; each k is a positive whole number; and digits only ever appear as repeat counts, so the decoded text has no digits of its own (you will never see something like 3a or 2[4]). The inputs are also chosen so that the decoded string is at most 105 characters long.
3[a] gives aaa and 2[bc] gives bcbc; written one after the other they make aaabcbc.Nesting Stack
nested input ➔ push the outer context on open ➔ pop and combine on close| 1 | def decode_string(s: str) -> str: |
| 2 | """Decode String: save the outer text and count at each '[', restore them at ']'. |
| 3 | Time: O(N * L) | Space: O(N + L) |
| 4 | """ |
| 5 | stack: list[tuple[str, int]] = [] # One saved (cur, num) per '[' still open |
| 6 | cur = "" # Text of the innermost open bracket, built so far |
| 7 | num = 0 # Repeat count being read, digit by digit |
| 8 | |
| 9 | for ch in s: |
| 10 | if ch.isdigit(): |
| 11 | # 1. Build The Repeat Count Digit By Digit: |
| 12 | # A count can have several digits, as in "12[a]", so each new digit shifts the earlier |
| 13 | # ones left by one place. |
| 14 | num = num * 10 + int(ch) |
| 15 | elif ch == "[": |
| 16 | # 2. Opener: Save The Outer State, Then Start The Inner One Empty: |
| 17 | # The outer text waits on stack with the count this bracket will use; resetting cur and num |
| 18 | # keeps the inner text from starting with the outer text already in it. |
| 19 | stack.append((cur, num)) |
| 20 | cur, num = "", 0 |
| 21 | elif ch == "]": |
| 22 | # 3. Closer: Restore The Outer State And Fold The Finished Inner Result In: |
| 23 | # The ']' closes the most recent '[', whose saved pair sits on top of stack; the inner text |
| 24 | # goes back after the outer text, repeated k times. |
| 25 | prev, k = stack.pop() |
| 26 | cur = prev + cur * k |
| 27 | else: |
| 28 | # 4. Plain Content Extends The Current Text: |
| 29 | # A letter belongs to whichever bracket is open right now. |
| 30 | cur += ch |
| 31 | |
| 32 | return cur |
stack holds one saved (cur, num) for every [ still open, innermost on top, and cur is the text of the innermost open bracket read so far.A [ starts a smaller problem inside the current one, and the outer text has to wait until that inner problem is finished: so at [ push the outer state (cur, num) onto stack and start the inner text empty, and at ] pop it back and fold the finished inner text in with cur = prev + cur * k. Brackets close in the reverse order they open, so the ] you meet always closes the most recent [ still open, and the top of stack is exactly what that [ saved; everything below it waits untouched for its own ]. That is the whole model for any nesting (brackets, parentheses, folders): last opened, first finished, one saved context per open level. The trap is the reset: stack.append((cur, num)) must be followed by cur, num = "", 0. Keep the old cur and the outer text is repeated inside the bracket ("3[a2[c]]" turns into "aacacaacacaacac"); keep the old num and the next count's digits are glued onto it (the inner 2 is read as 32).
See it run
Decode String, step by step
cur ""num 0stack empty
The top row is s. The bottom row is stack, filled from column 0, with the bottom on the left. Each saved pair is written as cur|num, and a dash means an empty text.
readthe character of s that the loop is readingdigita digit that is added to the count in numsavedthe pair (cur, num) that was just pushed onto stackpopthe saved pair that a closing bracket takes off stack
Start: s = "2[a10[b]]", cur = "", num = 0, and stack is empty.
Gotcha 1 of 5
- The trap
Gotcha 1: Keeping the old
curafter the pushMistakenum = 0Fixcur, num = "", 0What happens: At
[, the outer text is saved onstackwithstack.append((cur, num)). The inner text must then start empty. Ifcurkeeps the outer text, that text is also repeated inside the bracket. At], the outer text is added once more fromstack.Example: s = "3[a2[c]]"Mistake: returns 'aacacaacacaacac'Fix: returns 'accaccacc'
- Nothing opens or closes; each item only waits for the first later item that beats it, as in Daily Temperatures (LC 739). The stack then holds waiting items in sorted order and pops them when a bigger one arrives, instead of saving an outer context at an opener. See Next Greater Element
Deep Dive
Why the top of stack is the bracket that ] closes
A stack gives last in, first out order. Brackets close in the reverse order they open. So when the loop reads a ], the bracket it closes is the most recent [ that is still open. The top of stack is the pair that this [ saved.
At [, the loop pushes (cur, num). cur is the text built so far outside the new bracket. num is the repeat count that belongs to this bracket. The pair waits on stack while the inner text is built. Everything below it waits too, and nothing below it changes.
At ], the loop pops (prev, k) and sets cur = prev + cur * k. The inner text cur is finished, so it is repeated k times and added after the outer text prev. Then cur is the text of the bracket one level up.
Example: in Decode String (LC 394), s = "3[a2[c]]" decodes to "accaccacc". The inner 2[c] becomes "cc". The outer text "a" is put in front, which gives "acc". The outer count 3 repeats it, which gives "accaccacc". stack holds one pair after the first [, two pairs after the second [, and is empty again after the last ].
One trace: a two-digit count and the reset after the push
The board replays s = "2[a10[b]]". The top row is s. The bottom row is stack. A saved pair is written as cur|num, and a dash means an empty text.
The digits 1 and 0 build the count one digit at a time. num = num * 10 + int(ch) gives 1 and then 10. This step is marked as a trap on the board. With num = int(ch), the count would be 0.
At the second [, the loop pushes ("a", 10). The next step resets cur and num to "" and 0. This is the other trap on the board. Without the reset, cur would still be "a" inside the bracket, and num would still be 10.
The first ] pops ("a", 10) and sets cur = "a" + "b" * 10, which is 11 letters. The last ] pops ("", 2) and repeats those 11 letters two times. The answer has 22 letters.
What breaks when a reset or an order is wrong
Each wrong version below changes one line of decode_string. Each one gives a wrong answer without raising an error.
Keep cur after the push. For "3[a2[c]]", the inner text starts with the outer "a". The result is "aacacaacacaacac" and not "accaccacc".
Keep num after the push. For "1[2[a]]", the inner count 2 is added after the old 1 and is read as 12. The result is 12 letters a and not "aa".
Read the count with num = int(ch). For "10[a]", num becomes 1 and then 0, so the result is the empty string and not 10 letters a.
Read stack[-1] and do not pop it. The pair stays on stack, and the next ] uses the same pair again.
Write cur = cur * k + prev. The inner text is placed before the outer text. For "a2[c]", the result is "cca" and not "acc".
The cost, and other problems with the same stack
Let N be the length of s and L the length of the decoded text. The loop reads each character once. Each ] builds a new string of at most L letters, and there are at most N of them. So the time is O(N * L). stack holds at most one pair per open bracket, and cur holds at most L letters, so the space is O(N + L).
The decoded text can be much longer than s. The input "9[9[9[a]]]" has 10 characters and decodes to 729 letters.
Basic Calculator (LC 224) saves the running result and the sign at ( and restores them at ), with the same reset after the push. Simplify Path (LC 71) keeps a stack of folder names, and .. pops one. Valid Parentheses (LC 20) is the smallest case: it pushes the open bracket and pops it when the matching closing bracket arrives.
60-Second Pitch
"The input nests, so I use a stack. A [ starts a smaller problem inside the current one. I push the outer text and its count (cur, num) and start the inner text empty. A ] always closes the most recent [, so the top of the stack is exactly the pair that bracket saved. I pop it and set cur = prev + cur * k. I read counts as num * 10 + digit, and I reset cur and num after every push. The time is O(N * L) and the space is O(N + L), where L is the length of the decoded text."
Common Questions
- Why does a stack fit nested input?
Closing marks match the most recent opening mark that is still open. That is last in, first out order. The top of
stackis always the saved state of the bracket that the next]closes.- Why do you reset
curandnumafter the push? The outer text and count are already saved on
stack. The inner bracket must start with an empty text and no count. Ifcuris kept, the outer text is repeated inside the bracket. Ifnumis kept, the next count's digits are added to it.- How do you read a count such as 12?
Use
num = num * 10 + int(ch)for each digit. After1,numis 1. After2,numis 12. Settingnum = int(ch)keeps only the last digit.- What are the time and space complexity?
O(N * L) time and O(N + L) space, where
Nis the length ofsandLis the length of the decoded text. Each]builds a string of at mostLletters, andstackholds at most one pair per open bracket.- Could you solve it with recursion instead?
Yes. A recursive function can parse one bracket and return its text, and the call stack plays the role of
stack. The iterative version avoids deep recursion on a very deeply nested input, and it makes the saved state(cur, num)visible.
SWE Reasoning
Spot it
- The input nests: brackets inside brackets, parentheses inside parentheses, or folders inside folders.
- An inner part must be finished before the part around it can continue.
- The outer part has a state that must come back after the inner part ends, such as the text built so far and a repeat count.
- Closing marks match the most recent opening mark, so the order is last opened, first finished.
- A recursive solution would work, but it would use the call stack, and a long nested input could overflow it.
The invariant, step by step
stackstarts empty.curis the text of the innermost open bracket, andnumis the count being read.- A digit makes
num = num * 10 + int(ch), so a count with several digits is read correctly. - At
[, the loop pushes(cur, num)and then setscur, num = "", 0. Nowcuris the text of the new innermost bracket. - A letter is added to
cur, because it belongs to the bracket that is open now. - At
], the loop pops(prev, k)and setscur = prev + cur * k. The inner bracket is finished and merged into the outer one. - When the loop ends,
stackis empty andcurholds the whole decoded text.
Traps
- No reset of
curafter the push. The outer text is repeated inside the bracket."3[a2[c]]"gives"aacacaacacaacac". - No reset of
numafter the push. The next count is glued onto the old one."1[2[a]]"reads 12. - One digit at a time.
num = int(ch)loses the earlier digits of a count such as10. - Peek and not pop at
]. The saved pair is used by two brackets. - Wrong fold order.
cur * k + prevputs the inner text before the outer text. Useprev + cur * k. - Saving only one value. The pair must hold both
curandnum. If only one of them is saved, the outer bracket cannot be restored.