在这个问题中，我们需要通过重复添加总计数次数来解码给定的字符串。
我们可以采用三种不同的方法来解决问题，并且可以使用两个堆栈或一个堆栈来解决问题。另外，我们可以在不使用两个堆栈的情况下解决问题。
问题陈述 - 我们给出了一个字符串 str ，其中包含左括号和右括号、字母和数字字符。我们需要递归地解码字符串。
以下是解码字符串的模式或规则。
[chars] - “chars”应该在结果字符串中出现 count 次。
示例
输入
str = "2[d]3[c2[n]]";
输出
ddcnncnncnn
说明
首先，我们解码 2[n]，得到“2[d]3[cnn]”。
接下来，我们解码 3[cnn]。所以，我们得到“2[d]cnnncnncnn”。
接下来，我们解码 2[d]。所以，我们得到“ddcnnncnncnn”。
输入
5[i]
输出
iiiii
解释- 当我们解码给定的字符串时，我们得到 5 个“I”。
输入
3[fg]
输出
fgfgfg
解释- 当我们解码输入字符串时，我们得到“fg”3次。
方法 1
我们将使用两个堆栈来解决此方法中的问题。当我们得到一个左括号时，我们将其推入堆栈。此外，当我们获取数字字符时，我们将所有数字字符附加到一个有效的正整数并将它们添加到整数堆栈中。之后，当我们得到右括号时，我们从堆栈中弹出整数和字符。
算法
第 1 步- 定义“instSt”堆栈来存储数字，定义“strSt”来存储字符串字符和左括号。此外，初始化“answer”以存储结果字符串，初始化“tempStr”以存储临时字符串。
第 2 步- 开始遍历字符串。
第 3 步- 如果当前字符是数字，则用 0 初始化“num”以存储数字。
步骤 3.1 − 如果第 pth 索引处的字符是数字，则遍历字符串，直到得到字母字符或括号。在循环中，将“num”的先前值乘以 10，并将当前数字添加到其中。
步骤 3.2− 将“p”的值增加 1。
步骤 3.3 - 将数字值推送到“instSt”堆栈。
步骤 4 - 如果第 p 个索引处的字符是右括号，请按照以下步骤操作。
步骤 4.1- 用空字符串初始化“temp_str”。之后，如果‘instSt’不为空，则从堆栈中弹出顶部整数。
步骤 4.2 - 现在，使用循环，直到我们得到左括号或堆栈从“strSt”堆栈变空。另外，将字符附加到“temp_str”。
步骤 4.3 - 如果我们由于“[”而停止对角色进行大便，请将其删除。
步骤 4.4 - 接下来，我们需要在“answer”字符串中附加“temp_Str”“num”次。
步骤 4.5 - 将“answer”字符串的每个字符插入“strSt”堆栈中，并使用空字符串重新初始化它。
步骤 5 − 如果当前字符是左括号，请按照以下步骤操作。
步骤 5.1 − 如果前一个字符是数字，则将“[”推入堆栈“StrSt”。否则，将“[”压入 StrSt 堆栈，并将 1 压入“instSt”堆栈。
第 6 步− 如果我们得到一个字母字符，则将其推入“strSt”堆栈。
第 7 步- 最后，使用循环从“strSt”堆栈中删除所有字符，附加到“answer”字符串，然后返回它。
示例
#includeusing namespace std; string decodeTheString(string alpha) { stack instSt; stack StrSt; string tempStr = "", answer = ""; // Iterate the string for (int p = 0; p < alpha.length(); p++) { int num = 0; // If we find the number, extract the number and push it to the stack if (alpha[p] >= '0' && alpha[p] <= '9') { // Making iterations until we get an alphabetic character while (alpha[p] >= '0' && alpha[p] <= '9') { num = num * 10 + alpha[p] - '0'; p++; } p--; instSt.push(num); } // If the character at the pth index is closing bracket else if (alpha[p] == ']') { tempStr = ""; num = 0; // Pop the number from the stack if (!instSt.empty()) { num = instSt.top(); instSt.pop(); } // Pop the character until we get the opening bracket while (!StrSt.empty() && StrSt.top() != '[') { tempStr = StrSt.top() + tempStr; StrSt.pop(); } // remove the opening bracket if (!StrSt.empty() && StrSt.top() == '[') StrSt.pop(); // Append string to answer for num times for (int j = 0; j < num; j++) answer = answer + tempStr; // Insert the updated string again into the stack for (int j = 0; j < answer.length(); j++) StrSt.push(answer[j]); answer = ""; } // If the character at the pth index is an opening bracket else if (alpha[p] == '[') { if (alpha[p - 1] >= '0' && alpha[p - 1] <= '9') { StrSt.push(alpha[p]); } else { StrSt.push(alpha[p]); instSt.push(1); } } else { // Push alphabetic character in the string stack. StrSt.push(alpha[p]); } } // Pop all the elements, make a string, and return. while (!StrSt.empty()) { answer = StrSt.top() + answer; StrSt.pop(); } return answer; } // starting code int main() { string str = "2[d]3[c2[n]]"; cout << "The resultant string after decoding it is - " << decodeTheString(str) << endl; return 0; }
输出
The resultant string after decoding it is - ddcnncnncnn
时间复杂度− O(n^2)，因为我们遍历字符串并不断向堆栈推送和弹出元素。
空间复杂度− 在堆栈中存储元素的 O(n)。
方法2
我们将在这种方法中不使用堆栈来解决问题。另外，我们将使用reverse()方法来反转字符串。
算法
第 1 步- 开始迭代字符串。
第 2 步− 如果第 i 个字符是“]”，则将其推入“answer”字符串。否则，请按照以下步骤操作。
第 3 步- 使用空字符串初始化“temp_Str”。
第 4 步- 继续遍历“answer”字符串，直到该字符串为空或找到“[”字符。另外，继续从“answer”字符串中弹出最后一个字符并将其附加到“temp_Str”字符串中。
第 5 步- 当我们从找到“]”括号的位置向后遍历时，反转“temp_Str”字符串。
第 6 步- 从“answer”字符串中删除最后一个字符以删除“[”字符。
第 7 步- 如果“答案”字符串顶部包含数字，则使用数字生成一个整数，并将其存储在 number 变量中。
第 8 步- 反转数字字符串。
第 9 步- 使用 stoi() 方法将字符串转换为数字。
步骤 10 - 将 temp_Str 字符串附加到答案字符串“number”次。
第 11 步- 返回“答案”字符串。
示例
#includeusing namespace std; string decodeTheString(string alpha) { string answer = ""; // iterate the string characters for (int i = 0; i < alpha.length(); i++) { // for all other characters except the closing bracket if (alpha[i] != ']') { answer.push_back(alpha[i]); } else { // Extract the substring lying within the pair string temp_str = ""; // Keep on popping characters until '[' is found. while (!answer.empty() && answer.back() != '[') { temp_str.push_back(answer.back()); answer.pop_back(); } // get original string by reversing the string reverse(temp_str.begin(), temp_str.end()); // open bracket removal answer.pop_back(); // get integer value before the '[' character string number = ""; // get the number before opening bracket while (!answer.empty() && answer.back() >= '0' && answer.back() <= '9') { number.push_back(answer.back()); answer.pop_back(); } // reverse number string reverse(number.begin(), number.end()); // convert string to integer int numInt = stoi(number); for (int p = 0; p < numInt; p++) { answer += temp_str; } } } return answer; } int main() { string str = "2[d]3[c2[n]]"; cout << "The resultant string after decoding it is - " << decodeTheString(str) << endl; return 0; }
输出
The resultant string after decoding it is − ddcnncnncnn
时间复杂度− O(N^2)，因为我们遍历字符串并在循环内使用reverse()方法。
空间复杂度− O(N) 来存储数字和临时字符串。
