括号匹配问题

# 扩号匹配问题 【题目描述】 在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注。 【输入】 输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100。 【输出】 对每组输出数据，输出两行，第一行包含原始输入字符，第二行由"","?"和空格组成，"","?"和空格组成，""和"?"表示与之对应的左括号和右括号不能匹配。 【输入样例】 ((ABCD(x) )(rttyy())sss)( 【输出样例】 ((ABCD(x) .. )(rttyy())sss)( , ,. ### 【题目分析】：由于这里写的时候不能用钱号，就直接用点号代替，问号用逗号代替 ```cpp #include<cmath> #include<cctype> #include<cstdio> #include<cstring> #include<iostream> #include<set> #include<stack> #include<deque> #include<queue> #include<vector> #include<algorithm> //（（））说明要外面的括号匹配里面的括号也必须要匹配 不然的话里面的右括号就应该和最左边的左括号匹配 using namespace std; const int maxn=1000+5;//都看得懂 const char outc[]= {' ','$','?'};//要打印的东西 char a[maxn];//字符数组 int map[maxn],n;//n表示字符数组的长度 ， map表示栈，存下所左括号位置， 与右括号最近的左括号就是栈顶 int mark[maxn];//当前左括号的的状态 void find(int i,int dep)//递归做法 i表示位置，dep表示有几个未匹配的左括号，先假设左括号全未匹配 { // ( ( A B C D ( x ) // 0 1 2 3 4 5 6 7 8 // i==6, dep==3 // map: 0:0 1:1 2:6 // mark: 0 1 2 3 4 5 6 7 8 // 1 1 0 0 0 0 1 0 0 // i==8, dep==3 // mark [ map[dep-1] ]=0 // i==9 dep==2 // map: 0:0 1:1 // mark: 0 1 2 3 4 5 6 7 8 '\n' // 1 1 0 0 0 0 0 0 0 if(a[i]=='(')//如果找到一个左括号 { map[dep]=i;//标记一下 mark[i]=1;//标记一下 find(i+1,dep+1);//递归寻找下一个 } else if(a[i]==')')//如果找到一个右括号 { if(dep>0)//如果有左括号 { mark[map[dep-1]]=0;//将这个最近的左括号 的状态变为0 要减一因为数组从零开始的，第三个左括号改变状态 find(i+1,dep-1);//已经匹配了一个左括号，所以dep的个数要减一 } else//如果没有左括号用来匹配了 { mark[i]=2;//说明这个右括号不能匹配了 就赋值为2 find(i+1,0);//从下一个位置开始找 } } else if(i==n) return;//边界条件 else find(i+1,dep);//如果既不是左括号也不是右括号就直接跳过 } int main() { while(cin>>a) { cout<<a<<endl; n=strlen(a); find(0,0); for(int i=0; i<n; i++) { cout<<outc[mark[i]]; mark[i]=0; } cout<<endl; } return 0; } ```