数据结构实验之栈与队列四：括号匹配

￡神魔★判官ぃ 2022-05-18 03:11 194阅读 0赞

给你一串字符，不超过50个字符，可能包括括号、数字、字母、标点符号、空格，你的任务是检查这一串字符中的( ) ,\[ \],\{ \}是否匹配。

Input

输入数据有多组，处理到文件结束。

Output

如果匹配就输出“yes”，不匹配输出“no”

Sample Input

sin(20+10)
    {[}]

Sample Output

yes
    no

思路：只对字符串里面的括号进行操作，如果当前是左括号就把它记录到另外一个数组里，如果是右括号的话就把它与最近加入的左括号相比较，如果匹配的话，就top--，如果不匹配那么就说明这个字符串里的括号不匹配。

代码如下：

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int flag;
        char a[100];
    
        while(gets(a))
        {
            flag=1;
            stack<char>s;///一定要把栈的创建放在里面，不然多组输入会有问题；
            for(int i=0; a[i]!='\0'; i++)
            {
                if(a[i]=='('||a[i]=='{'||a[i]=='[')
                    s.push(a[i]);
                else if(a[i]==')'||a[i]=='}'||a[i]==']')
                {
                    if(s.empty())
                    {
                        cout<<"no"<<endl;
                        flag=0;
                        break;
                    }
                    else if((a[i]==']'&&s.top()=='[')||(a[i]=='}'&&s.top()=='{')||(a[i]==')'&&s.top()=='('))
                        s.pop();
                    else
                    {
                        cout<<"no"<<endl;
                        flag=0;
                        break;
                    }
                }
    
            }
            if(flag==1)
            {
                if(s.empty())
                    cout<<"yes"<<endl;
                else
                    cout<<"no"<<endl;
            }
        }
    }

还需要注意的是top==-1这一块为的就是避免（）\{ 这种情况的发生。