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

末蓝、 2022-06-07 08:54 169阅读 0赞

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

Time Limit: 1000MS Memory Limit: 65536KB

#### Problem Description ####

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

#### Input ####

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

#### Output ####

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

#### Example Input ####

sin(20+10)
    {[}]

#### Example Output ####

yes
    no

#include <bits/stdc++.h>
    
    using namespace std;
    #define intsize 100000
    #define addsize 100000
    typedef int elemtype;
    
    typedef struct
    {
        elemtype *base;
        elemtype *top;
        int stacksize;
    }sqstack;
    
    int initstack(sqstack &s)
    {
        //s.base = (elemtype *)malloc(intsize*sizeof(elemtype));
        s.base = new elemtype[intsize];
        if(!s.base) return -1;
        s.top = s.base;
        s.stacksize = intsize;
        return 0;
    }
    
    int bian(char n)
    {
        int flag;
        if(n=='(') flag = 1;
        if(n=='[') flag = 2;
        if(n=='{') flag = 3;
        if(n==')') flag = 4;
        if(n==']') flag = 5;
        if(n=='}') flag = 6;
        return flag;
    }
    
    void push(sqstack &s, int x)
    {
        /*if(s.top-s.base > s.stacksize)//栈满，追加存储空间
        {
            s.base = new elemtype[intsize+addsize];
            if(!s.base) return -1;
            s.top = s.base + addsize;
            s.stacksize += addsize;
        }*/
        *s.top++ = x;
    }
    
    int pop(sqstack &s)
    {
        elemtype x;
        return x = *--s.top;
    }
    
    /*void change(sqstack &s,char n)
    {
        int e1,e2;
        if(n=='+')
        {
            e1 = pop(s);
            e2 = pop(s);
            push(s,e1+e2);
        }
        else if(n=='-')
        {
            e1 = pop(s);
            e2 = pop(s);
            push(s,e2-e1);
        }
        else if(n=='*')
        {
            e1 = pop(s);
            e2 = pop(s);
            push(s,e1*e2);
        }
        else if(n=='/')
        {
            e1 = pop(s);
            e2 = pop(s);
            push(s,e2/e1);
        }
    }
    
    void show(sqstack &s)
    {
        while(s.top!=s.base)
        {
            cout << pop(s);
        }
        cout << endl;
    }*/
    
    int main()
    {
        sqstack s;
        char a[55],x;
        int n,flag;
        while(gets(a))
        {
            initstack(s);
            flag = 1;
            n = strlen(a);
            for(int i=0; i<n; i++)
            {
                x = a[i];
                if(x=='('||x=='['||x=='{')
                {
                    push(s,bian(x));
                }
                else if(x==')'||x==']'||x=='}' )
                {
                    if(s.top==s.base){flag=0;break;}
                    else if(bian(x)- pop(s) !=3)
                    {
                        flag = 0;break;
                    }
                }
            }
            if(s.top!=s.base){flag=0;}
            if(flag){cout << "yes" << endl; }
            else {cout << "no" << endl;}
        }
        //show(s);
        return 0;
    }