nyoj 15-括号匹配（二）模拟-白红宇

nyoj 15-括号匹配（二）模拟

阅读量：3904 次

发布时间：2019-05-23

本文共 1203 字，大约阅读时间需要 4 分钟。

题目描述:

给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。

如：

[]是匹配的

([])[]是匹配的

((]是不匹配的

([)]是不匹配的

输入描述:

第一行输入一个正整数N，表示测试数据组数(N<=10)每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100

输出描述:

对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行

样例输入:

复制

4[]([])[]((]([)]

样例输出:

分好几种情况。。。

模拟栈。。因为栈不能进行遍历，所以需要数组模拟。。。

1.如果为（或者[直接进入栈。。

2.如果为）或者]

（1）栈顶元素正好可以匹配时，则直接删除栈顶元素。。。

(2)不匹配时，则从栈顶开始依次遍历，直到找到匹配的位置，记下然后相当于将栈顶挪到了匹配的位置-1，然后记下之间的元素有多少个。。。

（3）如果（2）找不到元素，那直接答案+1。。。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn=105;int n;char ss[maxn];int ans;stack
        
         s;struct List{ int num; char a[maxn];};List L;void init(){ ans=0; L.num=0;}int main(){ scanf("%d",&n); while (n--) { init(); scanf("%s",ss); int len=strlen(ss); for (int i=0;i
         
          =0) { if(L.a[num-1]=='(') { flag=1; L.num=num-1; break; } else sum++; num--; } if(flag) ans+=sum; else ans++; } } else if(ss[i]==']') { if(L.num&&L.a[L.num-1]=='[') { L.num--; } else { int flag=0,sum=0,num=L.num; while (num>=0) { if(L.a[num-1]=='[') { flag=1; L.num=num-1; break; } else sum++; num--; } if(flag) ans+=sum; else ans++; } } } } ans+=L.num; printf("%d\n",ans); } return 0;}