#include <iostream> #include <string> #include<ctype.h> using namespace std; /* 思路： 此题可以将原字符串看成：数字和括号内的字符串，数字和单个字母 的这两个组合，就是重复输出括号内的字符串和单个字母的任务。 所以我们应该先将前面的数字字符串处理成数字，对于没有数字的情况，我们默认为1。 不难想到括号内的字符串我们可以用递归来实现，递归外应该用循环来遍历整个字符串，遇到单个字母我们直接输出； 其中因为只重复输出括号内的内容，我们应添加一个循环条件：非右括号才可以； 所以当我们遍历完整个括号内的字符串后，应该把右括号后一个位置的索引值赋给循环迭代的索引值， 说明我们括号内的字符串已经输出完毕，应当处理后面的字符串了。 */ string str; int dfs(int idx){ //循环内套递归，实质上仅遍历一次 char ch; int cnt; for (ch = str[idx++]; ch != ')' && idx < str.size(); ch = str[idx++]){ //因只单次处理括号的内容，所以设置右括号为跳出条件 for (cnt = 0; isdigit(ch); ch = str[idx++]) cnt = cnt * 10 + ch - '0'; // 是数字的情况 if (!cnt) cnt = 1; // //数字后不是左括号就是字母 if (ch == '('){ // 是左括号的情况，就递归输出cnt次的括号里的内容（哪怕前面无数字，cnt也为1） int tmp; while (cnt--) tmp = dfs(idx); idx = tmp; //匹配的右括号后面一个位置 } else while (cnt--) cout << ch; //是字母的情况，就输出cnt次的字母（哪怕前面无数字，cnt也为1） } if (ch == ')') return idx; } int main(){ int t; cin >> t; while (t--){ cin >> str; dfs(0); cout << endl; } system("pause"); return 0;
问题描述：在纺织CAD系统开发过程中，经常会遇到纱线排列的问题。
该问题的描述是这样的：常用纱线的品种一般不会超过25种，所以分别可以用小写字母表示不同的纱线，例如：abc表示三根纱线的排列；重复可以用数字和括号表示，例如：2(abc)表示abcabc；1(a)=1a表示a;2ab表示aab;如果括号前面没有表示重复的数字出现，则就可认为是1被省略了，如：cd(abc)=cd1(abc)=cdabc;这种表示方法非常简单紧凑，也易于理解；但是计算机却不能理解。为了使计算机接受，就必须将简单紧凑的表达方式展开。某ACM队接受了此项任务。现在你就是该ACM队的一员，请你把这个程序编写完成。
已知条件：输入的简单紧凑表达方式的长度不超过250个字符；括号前表示重复的数不超过1000；不会出现除了数字、括号、小写字母以外的任何其他字符；不会出现括号不配对等错误的情况（错误处理已由ACM其他队员完成了）。
思路：利用栈对括号进行存取
用递归的思想展开字符串：
1.for (ch = str[idx++]; ch != ')' && idx < str.size(); ch = str[idx++])
学习了一种新的使用for循环的形式，idx++先赋值再加1，括号里第1项和第3项使得字符一直向后遍历到结束。
2.if (!cnt) cnt = 1;
这种用法的意思是：如果cnt为0，则让cnt=1。
3.while (cnt--) cout << ch;
这种用法表示cnt自减到0（注意：是自减到0！），跳出循环。for（int n=3;n>0;n--）等价于 int n=3;while(n--){n>0}。