#P4080. 字符串解码
-
ID: 2321
Tried: 36
Accepted: 17
Difficulty: 5
-
算法标签>栈
字符串解码
题目内容
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encodedstring]，表示其中方括号内部的 encodedstring 正好重复 k次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a或 2[4]的输入。
输入描述
一个字符串k[encodedstring]
输出描述
输出一个经过解码的字符串
样例1
输入
3[a]2[bc]
输出
aaabcbc
样例2
输入
3[a2[c]]
输出
accaccacc
样例3
输入
2[abc]3[cd]ef
输出
abcabccdcdcdef
样例4
输入
abc3[cd]xyz
输出
abccdcdcdxyz
提示：
- 1<=s.length<=30
- s由小写英文字母、数字和方括号 '[]' 组成
- s保证是一个 有效 的输入。
- s中所有整数的取值范围为 [1,300]
题解
题面描述
给定一个经过编码的字符串，编码规则为：
k[encodedstring]
表示其中方括号内部的encodedstring正好重复k次。输入字符串保证有效，没有额外空格，且所有数字只表示重复次数，不会混淆成其他含义。
思路
本题的核心在于处理嵌套结构的解码问题。我们可以采用栈（stack）的方式解决：
- 当遇到数字时，将数字（可能多位）解析出来，并压入数字栈。
- 当遇到左括号[时，将当前结果字符串压入字符串栈，并将结果字符串置空以便处理括号内的新字符串。
- 当遇到右括号]时，从字符串栈中取出之前的结果，并从数字栈中取出重复次数，将当前字符串重复对应次数后与之前的字符串拼接。
- 如果遇到普通字符，则直接累加到当前结果中。
这种方法能够很好地处理嵌套和连续编码的情况。
代码分析
-
数字解析：
当遇到数字时，需要注意可能存在多位数。用count=count∗10+digit的方式累加计算数字。 -
栈的使用：
使用两个栈，一个存放重复次数（countStack），一个存放当前结果（resStack）。- 每遇到[，将当前字符串压入resStack，然后重置当前字符串。
- 每遇到]，从resStack中弹出字符串，并取出数字栈顶的重复次数，将当前字符串重复后拼接到弹出的字符串后。
-
遍历字符串：
通过下标遍历整个字符串，根据字符类型分别进行处理，直至遍历完成。 -
ACM模式输入输出：
主函数中通过输入输出流处理输入，符合ACM竞赛题目的格式要求。
C++
#include <iostream>
#include <stack>
#include <string>
using namespace std;
class Solution {
public:
// 解码函数，输入为编码后的字符串，返回解码后的结果字符串
string decodeString(string s) {
stack<int> countStack; // 用于存放重复次数
stack<string> resStack; // 用于存放当前已经解析的字符串
string res = ""; // 当前的结果字符串
int index = 0; // 遍历字符串的下标
while (index < s.size()) {
if (isdigit(s[index])) { // 如果遇到数字
int count = 0;
// 处理多位数
while (index < s.size() && isdigit(s[index])) {
count = count * 10 + (s[index] - '0');
index++;
}
countStack.push(count);
} else if (s[index] == '[') { // 遇到左括号，开始处理新的子串
resStack.push(res);
res = "";
index++;
} else if (s[index] == ']') { // 遇到右括号，回退并构造完整子串
string temp = resStack.top();
resStack.pop();
int repeatTimes = countStack.top();
countStack.pop();
// 将当前子串重复$repeatTimes$次，并与之前的字符串拼接
for (int i = 0; i < repeatTimes; i++) {
temp += res;
}
res = temp;
index++;
} else { // 遇到普通字符，直接累加
res.push_back(s[index]);
index++;
}
}
return res;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
// 循环读取输入字符串
while (cin >> s) {
Solution solution;
cout << solution.decodeString(s) << "\n";
}
return 0;
}
Python
# 定义解码函数，输入为编码后的字符串，返回解码后的字符串
class Solution:
def decodeString(self, s: str) -> str:
countStack = [] # 存放重复次数的栈
resStack = [] # 存放中间结果字符串的栈
res = "" # 当前结果字符串
index = 0 # 当前处理位置的下标
while index < len(s):
if s[index].isdigit(): # 如果字符为数字
count = 0
# 解析可能的多位数
while index < len(s) and s[index].isdigit():
count = count * 10 + int(s[index])
index += 1
countStack.append(count)
elif s[index] == '[': # 遇到左括号，压入当前结果
resStack.append(res)
res = ""
index += 1
elif s[index] == ']': # 遇到右括号，回退并构造完整字符串
temp = resStack.pop()
repeatTimes = countStack.pop()
res = temp + res * repeatTimes
index += 1
else: # 普通字符，直接添加到当前结果
res += s[index]
index += 1
return res
if __name__ == "__main__":
import sys
# 读取整个输入字符串
s = sys.stdin.read().strip()
solution = Solution()
result = solution.decodeString(s)
print(result)
Java
import java.util.*;
public class Main {
// 解码函数，输入为编码后的字符串，返回解码后的字符串
public String decodeString(String s) {
Stack<Integer> countStack = new Stack<>(); // 用于存放重复次数
Stack<String> resStack = new Stack<>(); // 用于存放中间结果字符串
String res = ""; // 当前结果字符串
int index = 0; // 当前处理位置的下标
while (index < s.length()) {
char ch = s.charAt(index);
if (Character.isDigit(ch)) { // 如果字符为数字
int count = 0;
// 处理可能的多位数字
while (index < s.length() && Character.isDigit(s.charAt(index))) {
count = count * 10 + (s.charAt(index) - '0');
index++;
}
countStack.push(count);
} else if (ch == '[') { // 遇到左括号，压入当前字符串
resStack.push(res);
res = "";
index++;
} else if (ch == ']') { // 遇到右括号，回退并构造完整字符串
String temp = resStack.pop();
int repeatTimes = countStack.pop();
StringBuilder sb = new StringBuilder(temp);
for (int i = 0; i < repeatTimes; i++) {
sb.append(res);
}
res = sb.toString();
index++;
} else { // 普通字符，直接累加
res += ch;
index++;
}
}
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取输入字符串并输出解码结果
while (sc.hasNext()) {
String s = sc.next();
Main solution = new Main();
System.out.println(solution.decodeString(s));
}
}
}