如何识别嵌套花括号并输出正确解码值？基于栈的字符串解码器问题

现有一个C++解码函数（如下），可处理单层花括号的编码字符串，但无法支持嵌套花括号场景。例如输入'ST4{4{3@9}}'时，无法正确解码嵌套部分。

原解码函数代码：

string decodeString(const string& encoded) {
    string decoded;
    int i = 0;
    while (i < encoded.length()) {
        if (isHexDigit(encoded[i])) {
            int repeatCount = stoi(string(1, encoded[i]), nullptr, 16);
            i++;
            if (encoded[i] == '{') {
                i++;
                string subString;
                while (i < encoded.length() && encoded[i] != '}') {
                    subString += encoded[i];
                    i++;
                }
                if (i == encoded.length() || encoded[i] != '}') {
                    throw InvalidInputException();
                }
                i++;
                for (int j = 0; j < repeatCount; j++) {
                    decoded += subString;
                }
            } else {
                throw InvalidInputException();
            }
        } else {
            decoded += encoded[i];
            i++;
        }
    }
    return decoded;
}

原函数逻辑：十六进制数字对应后续花括号内子串的重复次数，格式错误时抛出InvalidInputException。但遇到嵌套花括号时，会在第一个}处终止子串读取，导致嵌套部分未被解码。

基于栈的嵌套解码实现 #

要处理嵌套结构，核心是用栈保存当前解码上下文（已解码的前缀字符串、对应的重复次数）。遇到{时将当前状态入栈；遇到}时弹出栈顶状态，将当前子串重复指定次数后拼接到前缀字符串，作为新的当前解码结果。

实现代码如下：

#include <stack>
#include <cctype>
#include <stdexcept>

using namespace std;

class InvalidInputException : public runtime_error {
public:
    InvalidInputException() : runtime_error("Invalid input format") {}
};

string decodeString(const string& encoded) {
    string current_str;
    stack<pair<string, int>> st; // 保存(前缀字符串, 重复次数)
    int i = 0;
    int n = encoded.size();

    while (i < n) {
        if (isxdigit(encoded[i])) {
            // 读取连续十六进制数字（支持多位，比如"1A{abc}"表示重复26次）
            string num_str;
            while (i < n && isxdigit(encoded[i])) {
                num_str += encoded[i];
                i++;
            }
            int repeat_count = stoi(num_str, nullptr, 16);

            if (i >= n || encoded[i] != '{') {
                throw InvalidInputException();
            }
            i++; // 跳过'{'

            // 保存当前上下文，准备读取花括号内的子串
            st.push({current_str, repeat_count});
            current_str.clear();
        } else if (encoded[i] == '}') {
            if (st.empty()) {
                throw InvalidInputException(); // 存在未匹配的闭合花括号
            }
            auto [prev_str, count] = st.top();
            st.pop();

            // 重复当前子串并拼接到前缀字符串
            string repeated;
            for (int j = 0; j < count; j++) {
                repeated += current_str;
            }
            current_str = prev_str + repeated;
            i++;
        } else {
            // 普通字符直接追加到当前子串
            current_str += encoded[i];
            i++;
        }
    }

    if (!st.empty()) {
        throw InvalidInputException(); // 存在未闭合的花括号
    }

    return current_str;
}

代码说明 #

• 栈元素保存进入花括号前的已解码字符串和当前花括号对应的重复次数，实现嵌套上下文的切换
• 支持多位十六进制数字的重复次数，兼容原单数字场景的同时提升通用性
• 严格校验格式：未匹配的{/}、数字后无{等异常场景均抛出InvalidInputException
• 嵌套处理逻辑：遇到内层}时先完成内层解码，再回溯到外层处理重复操作

测试示例 #

输入"ST4{4{3{@9}}}"的解码流程：

1. 解码内层3{@9}，得到@9@9@9
2. 解码中层4{...}，将上述结果重复4次得到@9@9@9@9@9@9@9@9@9@9@9@9
3. 解码外层4{...}，将上述结果重复4次后拼接前缀ST，得到最终解码字符串

内容的提问来源于stack exchange，提问作者W H H