Decode nested strings and simplify paths

Why this matters

Two small jobs come up again and again in real programs. The first is expanding a short code into a longer text, such as turning 3[a2[c]] into accaccacc. The second is cleaning up a file path, such as turning /a/./b/../c into /a/c. Both jobs have the same shape. You read the input from left to right, and at some point you must set the current work aside, work on something inside it, and then come back to the work you set aside. A stack is the tool that holds the work you set aside, because the most recently set-aside item is always the first one you need back.

This lesson builds two small functions in C++. Both use a stack. You will trace each one by hand before you run it, so you can see what the stack holds at each step. The lesson assumes you know how to write a loop and a function, and that you have seen the stack operations push, pop and top in the lesson on stacks and balanced parentheses. The next lesson in this module builds a stack on a linked list.

Part one: repeat-count decoding

The rule

A repeat count is a number followed by a block in square brackets. The rule k[text] means that text appears k times in a row. So 3[a] means aaa, and 2[bc] means bcbc.

A nested block is one block placed inside another. In 3[a2[c]], the outer block is a2[c] with count 3. The inner block is c with count 2. Work from the inside out. The inner part 2[c] becomes cc. The outer block then reads a followed by cc, which is acc. Repeating acc three times gives accaccacc.

The difficulty is that a left-to-right reader sees the outer count before it sees the inner text. When it reads 3[, it must remember the 3 and the text that came before the bracket. Then it starts a fresh text for the inside of the bracket. When it reads ], the inside is finished, so it can repeat the inside text and join it to the remembered text. Each [ opens one level and each ] closes one level. The level that closes is always the most recently opened one. That is the stack rule: last opened, first closed.

So each stack entry holds two things: the count that goes with the open bracket, and the text that was built before that bracket. Call this pair a frame. A frame is pushed at each [ and popped at each ].

Worked example one: 3[a]2[bc]

This input has two blocks side by side, with no nesting. Here is what happens to the stack and the text, one character at a time. The table is a hand trace. It shows what the code in the next section does.

The first ] produces aaa, which becomes the text that was waiting on the stack for the second block. The second ] repeats bc and joins the result to aaa.

Worked example two: 3[a2[c]]

Now the nesting. The table shows the stack growing to two frames and then shrinking.

Notice that the first ] closes the inner block and leaves the outer frame on the stack. The second ] closes the outer block. The stack is empty at the end, which means every bracket was closed.

The code

The function below reads the input one character at a time. It keeps the current text in a std::string. It keeps the frames in a std::stack, which is the standard library's stack. A std::stack has the operations push, pop, top and empty, the same four operations you met earlier.

#include <cctype>
#include <iostream>
#include <stack>
#include <stdexcept>
#include <string>
#include <string_view>
 
std::string decode(std::string_view s) {
    struct Frame {
        int repeat;
        std::string prefix;
    };
    std::stack<Frame> frames;
    std::string current;
    int number = 0;
 
    for (char c : s) {
        if (std::isdigit(static_cast<unsigned char>(c))) {
            number = number * 10 + (c - '0');
        } else if (c == '[') {
            frames.push({number, current});
            number = 0;
            current.clear();
        } else if (c == ']') {
            if (frames.empty()) {
                throw std::invalid_argument("unmatched ']'");
            }
            Frame f = frames.top();
            frames.pop();
            std::string block;
            for (int i = 0; i < f.repeat; ++i) {
                block += current;
            }
            current = f.prefix + block;
        } else {
            if (number != 0) {
                throw std::invalid_argument("a count must be followed by '['");
            }
            current += c;
        }
    }
    if (!frames.empty()) {
        throw std::invalid_argument("missing ']'");
    }
    if (number != 0) {
        throw std::invalid_argument("a count must be followed by '['");
    }
    return current;
}

Read the code in four parts.

The Frame struct is defined inside the function because nothing else needs it. It holds the count and the text before the bracket.

The digit branch builds a number one digit at a time. Reading 1, then 0, gives number the value 1, then 10. The expression c - '0' turns the character '7' into the integer 7. The value of '0' in the character table is 48, so subtracting 48 from the character code gives the digit. Writing '0' instead of 48 makes the meaning clear.

The std::isdigit call is wrapped in static_cast<unsigned char>. The function isdigit expects a value between 0 and 255 or the special value EOF. A plain char can be negative on some machines, so the cast makes the value safe to pass.

The [ branch pushes the frame and resets both the number and the text. The ] branch pops the frame, builds the repeated block, and joins it to the saved prefix. The last branch handles ordinary letters. It adds the letter to the text, but first checks that no number is waiting. A number waiting in front of a letter, as in 2a, has no bracket and so cannot mean anything.

The checks after the loop report input that does not match. An extra ] is caught in the ] branch, because the stack is empty when it arrives. A missing ] is caught at the end, because a frame is still on the stack. A count left at the end, as in 3[a]2, is caught by one more check.

Running it

The main function below runs the decoder on several inputs, then on three bad inputs. The bad inputs are inside a try block, so that the program prints the message and keeps going.

int main() {
    const char* codes[] = {"3[a]2[bc]", "3[a2[c]]", "2[abc]3[cd]ef", "abc", "10[x]", "2[]x"};
    for (const char* code : codes) {
        std::cout << code << " -> " << decode(code) << '\n';
    }
    const char* bad[] = {"3[a", "a]", "2a"};
    for (const char* code : bad) {
        try {
            decode(code);
        } catch (const std::invalid_argument& e) {
            std::cout << code << " -> error: " << e.what() << '\n';
        }
    }
}

The program prints this, when compiled with g++ -std=c++20 -Wall and run:

3[a]2[bc] -> aaabcbc
3[a2[c]] -> accaccacc
2[abc]3[cd]ef -> abcabccdcdcdef
abc -> abc
10[x] -> xxxxxxxxxx
2[]x -> x
3[a -> error: missing ']'
a] -> error: unmatched ']'
2a -> error: a count must be followed by '['

Check the third line by hand. 2[abc] gives abcabc. 3[cd] gives cdcdcd. Then ef is added at the end. The joined result is abcabccdcdcdef, which matches.

Worked example three: a count of ten and a count of zero

The number 10 has two digits, and the decoder reads both. Reading 1 gives 1, and reading 0 gives 1 * 10 + 0, which is 10. So 10[x] repeats x ten times.

A count of zero is valid in this code. 2[]x produces an empty block twice, which is nothing, and then x is added. The output is x. If you want zero to be an error, add a check in the [ branch. The practice section asks you to do that.

Part two: simplifying file paths

What the path means

A path is text that names a place in a file system. The pieces are separated by /. Each piece is called a segment. The root of the file system is written as a single /.

Two special segments need care. The segment . means "this directory", so it changes nothing. The segment .. means "the directory one level up". A path such as /a/b/.. goes into a, then into b, then back up to a. The result is /a.

Empty segments also need care. A path like /home//foo/ has an empty segment between the two slashes, and a trailing slash at the end. Empty segments mean nothing, so they are removed.

The job is to turn any path into its simplest form. The simplest form has no ., no empty segments, and no .. that can be resolved. A .. at the root stays at the root, because there is no level above the root.

Why a stack

Read the segments from left to right. Each ordinary name is a directory you walked into. A .. means you walk back out of the most recent directory you walked into. The most recent one is the last one you entered. That is last in, first out. So you keep the names you have entered in a stack. A .. pops the top name. An ordinary name pushes a new name.

If the stack is empty and you see .., there is nothing to walk back out of, so the .. is ignored. That is the rule for the root.

Worked example: /a/./b/../../c/

This path has every kind of segment: a real name, a dot, a real name, two dot-dots, another real name, and a trailing slash. The table shows each segment and the stack after it is handled.

The stack holds c at the end. Join the names with a leading slash, and the result is /c.

The code

The function below reads the path one character at a time, the same way the decoder does. It collects the characters of each segment in a string called part. When it reaches a slash, it decides what to do with the finished segment. The last segment does not end with a slash in every input, so the loop runs one step past the end of the input and treats that step as a slash. That is a common trick: it makes the final segment go through the same code as all the others.

#include <cstddef>
#include <iostream>
#include <string>
#include <string_view>
#include <vector>
 
std::string simplify_path(std::string_view path) {
    std::vector<std::string> stack;
    std::string part;
    for (std::size_t i = 0; i <= path.size(); ++i) {
        char c = i < path.size() ? path[i] : '/';
        if (c != '/') {
            part += c;
            continue;
        }
        if (part.empty() || part == ".") {
            // nothing to do
        } else if (part == "..") {
            if (!stack.empty()) {
                stack.pop_back();
            }
        } else {
            stack.push_back(part);
        }
        part.clear();
    }
    std::string result;
    for (const auto& name : stack) {
        result += "/" + name;
    }
    return result.empty() ? "/" : result;
}

This code uses a std::vector as the stack. A vector can be used as a stack when you only add and remove at its end. push_back is the push, and pop_back is the pop. Using a vector here also makes the final join easy, because a loop can read the names from first to last.

The .. branch checks stack.empty() before it pops. That check is the root rule from above. The last line returns / when no names are left, so an empty path or a path that walks up past the root gives the root.

Running it

int main() {
    const char* paths[] = {"/home/", "/a/./b/../../c/", "/home//foo/", "/../", "/a/../../b/../c//.//", "/...", "/a/b/c/../.."};
    for (const char* p : paths) {
        std::cout << p << " -> " << simplify_path(p) << '\n';
    }
}

The output is:

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

The line /... -> /... is a useful check. The name ... is an ordinary name. It is not a dot and it is not a dot-dot. The code compares the whole segment with "." and with "..", not just the first character, so ... is kept.

Common mistakes

Forgetting to reset the number after [

The decoder keeps the count in a variable called number. After [, that count belongs to the frame that was just pushed, so it must be cleared. If the reset line is missing, the next letter appears to follow a count. The decoder then reports an error.

Here is what happens when the line number = 0; is deleted from the [ branch and the program is run on 3[a]2[bc]. The first call is not inside a try block, so the error ends the program:

terminate called after throwing an instance of 'std::invalid_argument'
  what():  a count must be followed by '['

The message is correct, because the number 3 is still in number when the a arrives. The code that checks for this is what turns a silent wrong answer into a visible error. Without that check, the program would have produced a wrong result without any sign of a problem.

Calling top() on an empty stack

The top() function returns the item on the top of the stack. On an empty stack there is no item, so calling top() is a bug. C++ says the result is undefined behaviour, which means the program is allowed to do anything at all. Sometimes it prints junk, sometimes it crashes.

The standard library has a debug mode that checks this. Compile with -D_GLIBCXX_ASSERTIONS and the check becomes an error message. The program below calls top() on an empty stack:

#include <iostream>
#include <stack>
 
int main() {
    std::stack<int> s;
    std::cout << s.top() << '\n';
}

Compiled with g++ -std=c++20 -Wall -D_GLIBCXX_ASSERTIONS, the program stops with a message like this one and exit code 134. The path and line number depend on the compiler version:

/usr/include/c++/15/bits/stl_stack.h:260: std::stack<_Tp, _Sequence>::reference std::stack<_Tp, _Sequence>::top() [with _Tp = int; _Sequence = std::deque<int, std::allocator<int> >; reference = int&]: Assertion '!this->empty()' failed.

The decoder avoids the problem by checking frames.empty() before it calls top() in the ] branch. The path code avoids it by checking stack.empty() before pop_back(). A pop_back() on an empty vector has the same kind of bug.

Comparing a signed int with a size

A common warning comes from writing a loop index as int when the length comes from size(). The size() function returns an unsigned type, and comparing a signed number with an unsigned one can give a wrong answer for negative values. The compiler warns about this when -Wall is on. This is the real warning for a short function:

#include <string>
#include <string_view>
 
int count_slashes(std::string_view path) {
    int n = 0;
    for (int i = 0; i < path.size(); ++i) {
        if (path[i] == '/') ++n;
    }
    return n;
}

Compiled with g++ -std=c++20 -Wall -c, the compiler prints:

sign.cpp: In function ‘int count_slashes(std::string_view)’:
sign.cpp:6:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::basic_string_view<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    6 |     for (int i = 0; i < path.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~

The fix is to use std::size_t for the index, as the simplify_path loop does. The warning is worth fixing, because a warning often points at a real bug.

Treating a name that starts with a dot as a dot

Some code checks part[0] == '.' to find dot segments. That check also catches ..., .hidden and ..x, which are ordinary names. Deleting them would change the path. The comparison with the whole text, part == "." and part == "..", is the correct check. The example /... -> /... above shows the expected result.

Practice

Exercise 1: Decode by hand

Decode 2[ab3[c]] without running the code. Write down the stack after each [ and ].

Show the answer

Read the outer block as ab followed by 3[c]. The inner 3[c] becomes ccc, so the text inside the outer brackets is abccc. The outer count is 2, so the result is abcccabccc. The stack holds (2, "") after the first [, then (2, "") and (3, "ab") after the second [. The first ] pops (3, "ab") and leaves (2, ""). The second ] pops (2, ""). The code prints abcccabccc, as a run confirms.

Exercise 2: Simplify by hand

Simplify /a//b/./../c/.. without running the code. Use a table like the one in the worked example.

Show the answer

The segments are a, an empty one, b, ., .., c, and ... Push a, skip the empty segment, push b, skip ., pop b for .., push c, then pop c for the final ... The stack holds a at the end, so the result is /a.

Exercise 3: Explain the empty-stack check

In the ] branch of decode, the code checks frames.empty() before it reads frames.top(). Explain what would happen if that check were removed, using the input a].

Show the answer

With the input a], the first character adds a to the text, and the stack is empty. The ] then arrives with no frame to pop. Without the check, top() would be called on an empty stack. That is undefined behaviour, so the program might crash or print junk. The check turns the case into the clear error unmatched ']'.

Exercise 4: What does an empty path return

What does simplify_path("") return, and which line of the function produces it?

Show the answer

It returns /. The loop runs once with the sentinel slash, and that slash finds an empty segment, which is skipped. The stack stays empty, so result is the empty string. The last line, return result.empty() ? "/" : result;, turns the empty string into /.

Exercise 5: Reject a count of zero

Change decode so that 0[a] throws std::invalid_argument with the message count must be at least 1. Write the change and say which branch it goes in.

Show the answer

Put the check in the [ branch, before the frame is pushed:

} else if (c == '[') {
    if (number == 0) {
        throw std::invalid_argument("count must be at least 1");
    }
    frames.push({number, current});
    number = 0;
    current.clear();
}

The check must come before the push and the reset. If it came after the reset, number would already be 0 and the check would be meaningless. Note that 2[]x still works, because its count is 2 and the block is empty.

Summary

• A stack holds work that you set aside, so the most recently set-aside item is the first one restored.
• In decoding, each [ pushes a frame with the count and the text so far, and each ] pops it and joins the repeated block.
• In path simplification, each ordinary name is pushed, and each .. pops the last name when the stack is not empty.
• Check that the stack is not empty before you read its top or pop it. Calling top() on an empty std::stack is undefined behaviour.
• Compare whole segments, not just first characters, so names such as ... are kept.