括号匹配问题

2018-01-28 11:07:59


扩号匹配问题

【题目描述】

在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序,找到无法匹配的左括号和右括号,输出原来字符串,并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注。

【输入】

输入包括多组数据,每组数据一行,包含一个字符串,只包含左右括号和大小写字母,字符串长度不超过100。

【输出】

对每组输出数据,输出两行,第一行包含原始输入字符,第二行由"","?"和空格组成,"","?"和空格组成,""和"?"表示与之对应的左括号和右括号不能匹配。

【输入样例】

((ABCD(x)

)(rttyy())sss)(

【输出样例】

((ABCD(x)

.. )(rttyy())sss)(

, ,.

【题目分析】:由于这里写的时候不能用钱号,就直接用点号代替,问号用逗号代替

#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;
}