Decode nested strings and simplify paths with a Python list

Why this matters

Some problems ask you to work through text that has layers. A pattern can sit inside another pattern. A folder path can go down into a folder and then climb back up. In both cases you enter something, then you must come back to where you were before. A stack is the tool for this, because it remembers the places you left, and the last place you left is the first one you return to.

The earlier lesson on balanced brackets used a stack to check that brackets match. This lesson uses a stack to hold text and numbers, not only bracket symbols. The second problem, path simplification, uses the stack as a list of folder names.

The idea: a stack is a pile of plates

A stack is a list where you only touch the top. You add to the top with push, you remove from the top with pop, and you look at the top with peek. The rule is last in, first out, often shortened to LIFO. The last item you pushed is the first one you pop.

Think of a pile of plates in a kitchen. You put a clean plate on the top. When you need a plate, you take the top one. You never reach into the middle of the pile.

In Python, a plain list is enough for a stack. append is push, pop() is pop, and stack[-1] is peek. A list is an ordered group of items that you can change, written with square brackets. len returns how many items a list holds, and an empty list is false when you test it with if. Here is a small example:

The output is:

top is plate 3
pop gives plate 3
pop gives plate 2
size now 1

Each append adds to the end of the list, so plate 3 is the top after the three appends. plates[-1] reads it without removing it. The first pop() removes plate 3, and the second removes plate 2. The check if not plates: is true when nothing is left to pop.

The key habit for this lesson is this: when you start something nested, push what you need to come back to. When you finish the nested part, pop it and continue.

Part 1: Decoding repeat patterns

Some compressed text uses a pattern like 3[abc]. It means "write abc three times", so the result is abcabcabc. The number in front is a repeat count, and the text inside the square brackets is repeated.

Patterns can be nested. In 3[a2[c]], the inside part a2[c] expands to acc, because c is written twice and then a comes before it. The outer part repeats that result three times:

3[a2[c]]  ->  a2[c] written 3 times  ->  acc acc acc  ->  accaccacc

The hard part is that the inner pattern is not finished until you reach the closing ]. When you see the opening [ for the inner part, you are in the middle of building the outer text. You must save the outer text and the outer count, start a fresh piece of text for the inner part, and later combine them.

Here is a step-by-step trace of 3[a2[c]]. The stack holds two things: the counts waiting for their ], and the text built so far outside each bracket.

read 3         number = 3
read [         push count 3, push outer text "", start new text, number = 0
read a         current text = "a"
read 2         number = 2
read [         push count 2, push outer text "a", start new text, number = 0
read c         current text = "c"
read ]         pop count 2, repeat "c" twice = "cc"
               pop outer text "a", current text = "a" + "cc" = "acc"
read ]         pop count 3, repeat "acc" three times = "accaccacc"
               pop outer text "", current text = "accaccacc"
end            return "accaccacc"

Look at the rhythm. Each [ pushes two things: the number that came before it and the text built so far. Each ] pops both, repeats the inner text, and joins it onto the saved outer text. The stack depth tells you how many brackets are still open.

Now the code. It walks through the string one character at a time. Each character is a one-letter string, and a for ch in s loop gives them in order.

Run it with python3. The output is:

3[a]2[bc] -> aaabcbc
3[a2[c]] -> accaccacc
2[abc]3[cd]ef -> abcabccdcdcdef
10[x] -> xxxxxxxxxx
2[2[2[z]]] -> zzzzzzzz

A few details matter here.

The count can have more than one digit. The line number = number * 10 + (ord(ch) - ord("0")) builds the number one digit at a time. When the code reads 1 and then 0, the number becomes 1, then 10. The built-in ord function returns the code number of a character, so ord("7") - ord("0") is 7. Python does not have a separate character type. A character is a string of length 1.

The test "0" <= ch <= "9" checks that the character is between the two digit characters. Python also has ch.isdigit(), but it is wider. It returns True for "²", a superscript two, which is not a count digit. The range test avoids that.

Plain letters go into current. Anything that is not a digit and not a bracket is treated as text. In this lesson the input only has letters and brackets, so that rule is enough.

The number variable is reset to 0 at each [. Without the reset, the next count would start from the wrong value.

Python strings can be repeated with *. "ab" * 3 returns ababab, and "ab" * 0 returns an empty string. Python strings have no repeat method, so this call fails:

print("ab".repeat(3))

Traceback (most recent call last):
  File "repeat_demo.py", line 1, in <module>
    print("ab".repeat(3))
          ^^^^^^^^^^^
AttributeError: 'str' object has no attribute 'repeat'

The last line names the error type, AttributeError, and the reason. The file name depends on where you save the program.

Strings in Python cannot be changed in place. current += ch makes a new string each time, which is fine for the short texts in this lesson. For a very long text, the usual Python method is to collect the pieces in a list and call "".join(pieces) once at the end.

A second example, with letters between brackets

Here is a harder input: 2[abc]3[cd]ef. There are two separate patterns, and then plain letters at the end. The stack empties after each closing bracket, so the code never has more than one pattern open at a time:

read 2, [      push 2, save "" , current = ""
read abc       current = "abc"
read ]         pop 2, chunk = "abcabc", current = "" + "abcabc" = "abcabc"
read 3, [      push 3, save "abcabc", current = ""
read cd        current = "cd"
read ]         pop 3, chunk = "cdcdcd", current = "abcabc" + "cdcdcd"
read ef        current = "abcabccdcdcdef"

The result is abcabccdcdcdef. The stack depth went 0, 1, 0, 1, 0. Two levels of nesting never happened, so the stack never held more than one saved text at once.

A third example, deeper nesting

Now 2[2[2[z]]]. Three levels of brackets, all with count 2. The stack depth reaches three. Each [ pushes the count and the text so far. The innermost z is repeated twice first. Then that result is repeated twice by the middle level, then twice again by the outer level. Two times two times two is eight, so the output has eight z characters:

zzzzzzzz

The count of letters in the final answer is the product of all the counts that enclose the letter. That is a useful way to check your work. Multiply the counts that wrap a letter, and you have how many copies of it appear.

Why a stack and not recursion

Recursion, where a function calls itself, can also decode nested patterns. The stack version does the same job with a loop, and its memory use is a plain list you can inspect. A recursive version uses the call stack, which has a limit. In Python the default limit is 1000 nested calls. sys.getrecursionlimit() returns that number, and when a call goes deeper, Python raises a RecursionError. A recursive version can hit that limit on deeply nested input, while the loop version does not. Recursion is covered in its own lesson, so this lesson stays with the explicit stack.

Part 2: Simplifying a Unix-style file path

A path names a place in a folder tree. On Linux and macOS, folders are separated by /. The path /home/user/notes starts at the root, which is the top folder, then goes into home, then user, then notes.

Two special names make paths harder:

• . means "this folder". It does nothing, so /a/./b is the same as /a/b.
• .. means "the parent folder", one level up. So /a/b/.. is the same as /a.

Other rules matter too. Two slashes in a row, such as //, count as one slash. A slash at the end does not change the place. And .. at the root stays at the root, because there is no folder above it.

The task is: given a messy path, return the shortest path that points to the same place. For example, /a/./b/../../c/ should become /c.

Splitting the path into parts

The string method split("/") cuts a string at each slash and returns a list of the pieces. Look at what it gives for /a/./b/../../c/:

print("/a/./b/../../c/".split("/"))

['', 'a', '.', 'b', '..', '..', 'c', '']

The first part is empty because the path starts with a slash. The last part is empty too, because the path ends with a slash. Empty parts and . parts are ignored. Every other part is a folder name, or a .. that climbs up.

The stack holds the folder names from the root down to the current place. The end of the list is the innermost folder. A normal name is appended. A .. pops the last item, which moves you up one level. If the list is already empty, you are at the root, so .. does nothing.

Here is the trace for /a/./b/../../c/:

part    action    stack (bottom to top)
""      skip      []
"a"     push      [a]
"."     skip      [a]
"b"     push      [a, b]
".."    pop       [a]
".."    pop       []
"c"     push      [c]
result  /c

At the end, the stack holds c alone. The answer is / followed by each name from the first item to the last.

The code

The output is:

/home/ -> /home
/a/./b/../../c/ -> /c
/../ -> /
/a//b////c/d//././/.. -> /a/b/c
/... -> /...
/a/../../b/../c//.// -> /c

Read the lines one at a time:

• /home/ keeps home and drops the trailing slash.
• /../ tries to go above the root, and the .. on an empty stack does nothing. The answer is the root.
• /a//b////c/d//././/.. has many empty parts. They are skipped. d is pushed, then . is skipped, then .. pops d, so the stack is a, b, c.
• /... stays as it is. Three dots is an ordinary folder name, not a parent reference. Only exactly .. climbs up.

Why the order is easy in Python

A Python list keeps items in the order they were added. The first item is at the front, and the last item is at the end. A for loop over the list goes from the first item to the last, which is the bottom of the stack to the top. The path needs the root first, so the list can be joined as it is:

The output is:

plain for: /a/b/c
list: ['a', 'b', 'c']

In the Java version of this lesson, a stack was read from its top down, so the path needed an extra step to walk it from the bottom. A Python list needs no such step.

A third path example

The input /a/../../b/../c//.// tests two things at once: climbing above the root, and empty parts at the end. The steps are: a is appended, the first .. pops it, the second .. finds the stack empty and does nothing, b is appended, the next .. pops it, c is appended, and the last parts are skipped. The stack is c alone, so the answer is /c. The program printed exactly that.

Common mistakes

Popping an empty stack

A closing bracket with no opening bracket makes the decoder pop an empty list. Here is the real error from running decode("]") with the same decode function as above, saved in a file called pop_demo.py:

Traceback (most recent call last):
  File "pop_demo.py", line 22, in <module>
    print(decode("]"))
  File "pop_demo.py", line 15, in decode
    times = counts.pop()
IndexError: pop from empty list

The traceback is shortened here: Python also prints a line of ~ and ^ marks under each call, which points at the exact part of the line. The last line says what went wrong: IndexError, which means you asked for an item at a position that is not there. The lines above it show where. The exception came from pop inside decode, at line 15 of pop_demo.py. An exception is an error that stops the program, and the name before the colon tells you its type. The fix is to check counts before popping, and raise a clear message if it is empty. The practice section below does this.

Forgetting that a missing bracket is not an error

The decoder above does not check the end of the string. An unclosed bracket gives a wrong answer without any error:

print(decode("3[a"))

a

The program printed a, which is wrong. The correct answer would need aaa, but the closing bracket never arrived, so the count 3 was never used. The list counts still holds one saved count when the loop ends. The fix is a check after the loop: if counts is not empty, some bracket was never closed.

Forgetting to save the outer text

The most common mistake in the decoder is to skip the line that saves the text before the [. Without it, the text before a pattern is lost when the pattern begins. The stack is the only place that remembers the outer text, so it must be appended at every [. Check each [ in your code against the trace table above.

Treating ... as a parent reference

Only the exact text .. climbs up. A name like ... or ..bak is a normal folder name. A check that uses startswith("..") would be wrong, because it would also catch ..bak.

Using is to compare strings

Use part == ".." and not part is "..". The == operator asks whether two strings have the same letters. The is operator asks whether two names point to the same object in memory. Python sometimes shares one object between equal strings, but that is not something your code can count on. Here is a case where the two answers differ:

x = "".join(["..", ""])
print(x == "..")
print(x is "..")

True
False

Python 3.14 also prints a warning for the second line when it is read:

SyntaxWarning: "is" with 'str' literal. Did you mean "=="?

Always use == for text.

Practice

Exercise 1: decode by hand

Decode 2[a1[b]]c on paper, using the trace style from this lesson. Write the stack at each step.

Show the answer

The inner pattern 1[b] is b. The text a followed by b is ab. The outer pattern repeats ab twice, giving abab. The plain c at the end is added, so the answer is ababc. The stack reaches depth two at the inner [, then falls to depth one after the first ], and to depth zero after the second ]. The function decode returns ababc for that input.

Exercise 2: simplify a path

Simplify /home//foo/../bar/. and write the stack after each part.

Show the answer

The parts are home, empty, foo, .., bar, .. The stack goes [home], then [home, foo], then .. pops to [home], then bar gives [home, bar]. The . is skipped. The answer is /home/bar. The function simplify returns /home/bar.

Exercise 3: reject a stray closing bracket and an unclosed bracket

Change decode so that it raises a ValueError in both cases: a ] with nothing open, and a [ that is never closed. The message should say which problem it is.

Show the answer

Use enumerate so the loop knows the index, add a check before the pop in the ] branch, and add a check after the loop. This is the full function:

def decode_checked(s):
    counts = []
    outers = []
    current = ""
    number = 0
    for i, ch in enumerate(s):
        if "0" <= ch <= "9":
            number = number * 10 + (ord(ch) - ord("0"))
        elif ch == "[":
            counts.append(number)
            outers.append(current)
            current = ""
            number = 0
        elif ch == "]":
            if not counts:
                raise ValueError(f"unmatched ] at index {i}")
            times = counts.pop()
            current = outers.pop() + current * times
        else:
            current += ch
    if counts:
        raise ValueError("unclosed [")
    return current

Running these inputs gives decode_checked("2[a1[b]]c") returns ababc. Running decode_checked("3[a") raises ValueError: unclosed [, and running decode_checked("a]") raises ValueError: unmatched ] at index 1.

Exercise 4: predict a path that climbs too high

What does simplify("/a/b/../../../c") return? Explain why the third .. does no harm.

Show the answer

The parts are a and b, which gives the stack [a, b]. The first .. pops b, and the second pops a. The stack is now empty, so the third .. finds nothing to pop and does nothing. Then c is appended, giving /c. The function returns /c. The third .. is harmless because the empty stack means the root, and you cannot go above the root.

Exercise 5: count the letters

Without running the program, predict how many z characters decode("2[3[z]2[y]]") produces, then check by running it.

Show the answer

The inner 3[z] is zzz. The inner 2[y] is yy. The outer pattern contains zzzyy, and it repeats twice, giving zzzyyzzzyy. That has six z characters. The rule "multiply the counts that wrap a letter" gives the same result: z is wrapped by 2 and 3, so 2 times 3 is 6. The function returns zzzyyzzzyy.

Summary

• A stack is last in, first out. In Python a list does the job: append pushes, pop() pops, and [-1] reads the top.
• When a nested pattern starts with [, push the count and the text built so far, then pop them at ] and combine.
• Each path part is handled in order: skip empty parts and ., pop for .. if the stack is not empty, and append every other name.
• A Python list is read from the first item to the last, so a stack of folder names can be joined into a path without reversing it.
• Check for an empty stack before pop(), and check for leftover open brackets after the loop.