题目链接:http://ac.jobdu.com/problem.php?pid=1153
题目描述:
-
在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序,找到无法匹配的左括号和右括号,输出原来字符串,并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.
- 输入:
-
输入包括多组数据,每组数据一行,包含一个字符串,只包含左右括号和大小写字母,字符串长度不超过100。
注意:cin.getline(str,100)最多只能输入99个字符!
- 输出:
-
对每组输出数据,输出两行,第一行包含原始输入字符,第二行由"$","?"和空格组成,"$"和"?"表示与之对应的左括号和右括号不能匹配。
- 样例输入:
-
)(rttyy())sss)(
- 样例输出:
-
)(rttyy())sss)( ? ?$
已AC代码:
#include<stdio.h> struct Node{ char str; int sub; }; char str1[101]; //用来存储输入的字符串 struct Node stack[101]; //用来括号匹配的栈 int j; //栈的下标 struct Node node[101]; int main(void) { //用来存放字符以及下表 for(int i=0;i<101;i++) //输出修正后的串 { str1[i]='\0'; } while(scanf("%s",str1)!=EOF) { j=-1; int i=0; int n;//用来存储字符串的长度 while(str1[i]!='\0'){i++;} n=i; for(i=0;i<n;i++) { node[i].str=str1[i]; node[i].sub=i; } for(i=0;i<n;i++) { if(node[i].str=='(') //如果是左括号,直接入栈 { stack[++j]=node[i]; } else if(node[i].str==')') //如果是右括号,则看栈是否为空,并且栈里有没有匹配的左括号 { if(j!=-1&&stack[j].str=='(') // 有匹配的左括号,则出栈,更改字符 { node[i].str=' '; node[stack[j].sub].str=' '; j--; } else //没有匹配的左括号,则入栈 { stack[++j]=node[i]; } } else { node[i].str=' '; } } while(j!=-1) //修改Node节点下标为stack[j].sub的字符 { if(stack[j].str=='(') { node[stack[j].sub].str='$'; } else { node[stack[j].sub].str='?'; } j--; } printf("%s",str1); //输出原串 printf("\n"); str1[n]='\0'; for(i=0;i<n;i++) //输出修正后的串 { printf("%c",node[i].str); } printf("\n"); for(i=0;i<101;i++) //输出修正后的串 { str1[i]='\0'; } } return 0; }