1203：扩号匹配问题
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注。
【输入】
输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100。
【输出】
对每组输出数据，输出两行，第一行包含原始输入字符，第二行由"$","?"和空格组成，"$"和"?"表示与之对应的左括号和右括号不能匹配。
【输入样例】
((ABCD(x)
)(rttyy())sss)(
【输出样例】
((ABCD(x)
$$
)(rttyy())sss)(
? ?$
【来源】
No
1. #include<stdio.h> 2. #include<iostream> 3. #include<cstring> 4. using namespace std; 5. char a[101],b[101]; 6. int up(int c) 7. { 8. if(c==-1) return -1;//结束点 9. else if(b[c]=='$') return c;//找到返回位置 10. else return up(c-1);//向前寻找 11. } 12. int main() 13. { 14. while(scanf("%s",a)!=-1){//重复读取直到读取失败 15. printf("%s\n",a); 16. int n=strlen(a); 17. memset(b,' ',sizeof(b));//初始化为空格 18. for(int i=0;i<n;i++){ 19. if(a[i]=='(') b[i]='$';//'('标记 20. else if(a[i]==')'){ 21. int m=up(i-1);//寻找对应位置点 22. if(m==-1) b[i]='?';//无匹配 标记位置点 23. else b[m]=' ';//有匹配 取消标记 24. } 25. } 26. printf("%s\n",b); 27. } 28. return 0; 29. }
1. #include<cstdio> 2. #include<iostream> 3. #include<cstring> 4. using namespace std; 5. int l,i,top,a[101],b[101]; 6. string s; 7. int main() 8. { 9. while(getline(cin,s)){//重复读取一行字符串 10. top=0; 11. l=s.size(); 12. memset(a,0,sizeof(a)); 13. memset(b,0,sizeof(b)); 14. for(i=0;i<l;i++){ 15. if(s[i]=='('){ 16. top++; 17. a[top]=i;//遇'('入栈 18. b[i]=1;//标记 19. } 20. if(s[i]==')'){ 21. b[i]=2; 22. if(top>0){ 23. b[a[top]]=0;//取消'('标记 24. b[i]=0;//取消')'标记 25. top--;//出栈 26. } 27. } 28. } 29. cout<<s<<endl; 30. for(i=0;i<l;i++){ 31. if(b[i]==0) cout<<" "; 32. if(b[i]==1) cout<<"$"; 33. if(b[i]==2) cout<<"?"; 34. } 35. cout<<endl; 36. } 37. return 0; 38. }
