- 题目链接：http://noi.openjudge.cn/ch0202/2705/
- 总时间限制:1000ms内存限制:65536kB
- 描述
- 在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.
- 输入
-
输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，
字符串长度不超过100
注意：cin.getline(str,100)最多只能输入99个字符！ - 输出
- 对每组输出数据，输出两行，第一行包含原始输入字符，第二行由"$","?"和空格组成，"$"和"?"表示与之对应的左括号和右括号不能匹配。
- 样例输入
-
((ABCD(x) )(rttyy())sss)(
- 样例输出
-
((ABCD(x) $$ )(rttyy())sss)( ? ?$
非递归写法：（用栈模拟）
代码来源：http://blog.csdn.net/sjf0115/article/details/8675934
思路：
1 #include<stdio.h> 2 #include<iostream> 3 #include<stack> 4 #include<string.h> 5 using namespace std; 6 7 int main() 8 { 9 int i; 10 char str[101],Mark[101]; 11 while(scanf("%s",str) != EOF) 12 { 13 stack<char> S; 14 for(i = 0;i < strlen(str);i++) 15 { 16 //如果是'('则入栈 17 if(str[i] == '(') 18 { 19 //将数组下表暂存在栈中 20 S.push(i); 21 //对应输出字符串暂且为' ' 22 Mark[i] = ' '; 23 } 24 else if(str[i] == ')') 25 { 26 //如果没有'('相匹配 27 if(S.empty()) 28 { //对应输出字符串改为'?' 29 Mark[i] = '?'; 30 } 31 else//有'('相匹配 32 { 33 //对应输出字符串改为' ' 34 Mark[i] = ' '; 35 //栈顶位置左括号与其匹配，弹出已经匹配的左括号 36 S.pop(); 37 } 38 } 39 //其他字符需许考虑,与括号无关 40 else 41 { 42 Mark[i] = ' '; 43 } 44 }//for 45 //若栈非空，则有没有匹配的左括号 46 while(!S.empty()) 47 { 48 //对应输出字符串改为'$' 49 Mark[S.top()] = '$'; 50 S.pop(); 51 } 52 Mark[i] = '\0'; 53 //输出 54 puts(str); 55 puts(Mark); 56 } 57 return 0; 58 }
递归写法：
（代码来源：http://blog.csdn.net/dreamchaseryx/article/details/41213459）
思路：在每一个递归层次都扫描剩余的字符串，遇到左括号进入下一层递归；遇到右括号则标记空格，并返回右括号下一个位置的下标；否则标记该左括号为匹配失败。
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 5 int pp(int); 6 char c[300] = 7 { }; 8 int l; 9 int main() 10 { 11 12 while (cin.getline(c, 120)) 13 { 14 cout<<c<<endl; 15 l = strlen(c); 16 int i; 17 for (i = 0; i < l; i++) 18 if (c[i] != '(' && c[i] != ')') 19 c[i] = ' '; 20 i = 0; 21 while (c[i] != 0) 22 { 23 while (c[i] != '(' && c[i] != 0) 24 i++; 25 if (c[i] == '(') 26 i = pp(i); 27 } 28 i = 0; 29 while (c[i] != 0) 30 { 31 if (c[i] == ')') 32 c[i] = '?'; 33 i++; 34 } 35 cout << c << endl; 36 } 37 return 0; 38 } 39 40 int pp(int pos) 41 { 42 int i; 43 i = pos + 1; 44 while (1) 45 { 46 while (c[i] != '(' && c[i] != ')' && c[i] != 0) 47 i++; 48 if (c[i] == '(') 49 { 50 i = pp(i); 51 } 52 else if (c[i] == ')') 53 { 54 c[pos] = ' '; 55 c[i] = ' '; 56 return i + 1; 57 } 58 else 59 { 60 c[pos] = '$'; 61 return l; 62 } 63 } 64 }
