- 总时间限制: 1000ms 内存限制: 65536kB
- 描述
- 在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.
- 输入
-
输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，
字符串长度不超过100
注意：cin.getline(str,100)最多只能输入99个字符！ - 输出
- 对每组输出数据，输出两行，第一行包含原始输入字符，第二行由"$","?"和空格组成，"$"和"?"表示与之对应的左括号和右括号不能匹配。
- 样例输入
-
((ABCD(x) )(rttyy())sss)(
- 样例输出
-
((ABCD(x) $$ )(rttyy())sss)( ? ?$
题目链接：http://ica.openjudge.cn/function2/5/
分析：主要是用到栈，这里用数组直接模拟即可。栈里面保存字符串中左括号的下标。扫描字符串，遇到左括号则下标入栈，遇到右括号则检验栈是否为空，不为空则出栈并将对用的左右括号字符位置标记空格，否则将右括号字符对应位置标记“?”。
扫描完成以后，再扫描栈，把多余的左括号字符对应位置标记“$”.
代码：
1 #include<stdio.h> 2 #include<string.h> 3 int main(int argc, char *argv[]) 4 { 5 char str[110]; 6 int len,i,k; 7 int stack[110],end=0; 8 while(scanf("%s",str)!=EOF) 9 { 10 printf("%s\n",str); 11 end=0; 12 len=strlen(str); 13 for(i=0;i<len;i++) 14 { 15 if(str[i]!='('&&str[i]!=')') str[i]=' '; 16 } 17 for(i=0;i<len;i++) 18 { 19 if(str[i]=='(') 20 { 21 stack[end]=i; 22 end++; 23 } 24 else if(str[i]==')') 25 { 26 if(end>0)//栈不为空，则 27 { 28 k=stack[end-1]; 29 str[k]=' ';//栈顶的左括号和新遇到的右括号匹配 30 str[i]=' '; 31 end--;//栈顶元素出栈 32 } 33 else 34 { 35 str[i]='?';//右括号不匹配 36 } 37 } 38 } 39 while(end>0) 40 { 41 k=stack[end-1]; 42 str[k]='$'; 43 end--; 44 } 45 printf("%s\n",str); 46 } 47 return 0; 48 }
递归的代码：
递归的思路可以参考“排队游戏”这一题的递归代码：http://www.cnblogs.com/huashanqingzhu/p/7238768.html
1 #include<stdio.h> 2 #include<string.h> 3 int fun(char *str,int len,int nowIndex);//nowIndex表示当前扫描到的字符下标。返回右括号的下标或-1 4 int count=0;//表示当前已经递归保存的左括号的个数 5 int main(int argc, char *argv[]) 6 { 7 char str[110]; 8 int len,i,k; 9 while(scanf("%s",str)!=EOF) 10 { 11 printf("%s\n",str); 12 len=strlen(str); 13 for(i=0;i<len;i++) 14 { 15 if(str[i]!='('&&str[i]!=')') str[i]=' '; 16 } 17 count=0; 18 fun(str,len,0); 19 printf("%s\n",str); 20 } 21 return 0; 22 } 23 int fun(char *str,int len,int nowIndex)//nowIndex表示当前扫描到的字符下标。返回右括号的下标或-1 24 { 25 int temp; 26 if(nowIndex<len) 27 { 28 if(str[nowIndex]==')') 29 { 30 if(count>0) 31 return nowIndex; 32 else 33 { 34 str[nowIndex]='?'; 35 return fun(str,len,nowIndex+1); 36 } 37 } 38 else if(str[nowIndex]==' ') 39 return fun(str,len,nowIndex+1); 40 else 41 { 42 count++; 43 temp=fun(str,len,nowIndex+1);//获取当前左括号对应的右括号 44 if(temp!=-1) 45 { 46 str[temp]=' '; 47 str[nowIndex]=' '; 48 count--; 49 return fun(str,len,temp+1); 50 } 51 else 52 { 53 str[nowIndex]='$';//temp==-1表示当前的左括号是多余的，不可匹配的 54 return -1; 55 } 56 } 57 } 58 return -1; 59 }
