括号匹配问题

2018-01-28 11:07:59


扩号匹配问题

【题目描述】

在某个字符串(长度不超过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; }