括号匹配

╰半橙微兮° 2022-03-30 02:28 269阅读 0赞

###  ###

题目描述

假设一个算术表达式中可以包含三种括号：圆括号“(”和“)”，方括号“\[”和“\]”和花括号“\{”和“\}”，且这三种括号可按任意的次序嵌套使用（如：…\[…\{… …\[…\]…\]…\[…\]…(…)…)。编写判别给定表达式中所含括号是否正确配对出现的算法。输出结果YES 或者 NO。

输入

5+\{\[2X5\]+2\}

输出

YES

样例输入 Copy

8-\[\{2+7\]\}

样例输出 Copy

##### 分析： #####

此题用栈可以很好的解决。可以先经过一次预处理将括号保存到一个新的数组里面。然后用栈 ，

#include"stdio.h"
    #include"string.h"
    typedef struct
    {
        char symobl[10000];
        int top;
    } SYM;
    SYM a;
    void POP(char *e)
    {
    
        *e=a.symobl[a.top-1];
        a.top--;
    
    }
    void PUSH(char e)
    {
    
        a.symobl[a.top]=e;
        a.top++;
    }
    int Serch(char symobl[])
    {
        int i,j,k,len,mark=1;
        char e;
        len=strlen(symobl);
    
        for(i=0; i<len; i++)
        {
            if(symobl[i]==')'||symobl[i]==']'||symobl[i]=='}')
            {
                POP(&e);
                if(symobl[i]==')')
                {
                    if(e!='(')
                        mark=0;
                }
                else if(symobl[i]==']')
                {
                    if(e!='[')
                        mark=0;
                }
                else if(symobl=='}')
                {
                    if(e!='{')
                        mark=0;
                }
    
            }
            else
                PUSH(symobl[i]);
        }
        if(a.top!=0)
            mark=0;
    
        return mark;
    }
    int main()
    {
        char word[10000];
        char symobl[10000];
        int i,j,k,mark,l;
        while(gets(word)!=NULL)
        {
            j=0;
            a.top=0;
            l=strlen(word);
            for(i=0; i<l; i++)
                if(word[i]=='('||word[i]==')'||word[i]=='['||word[i]==']'||word[i]=='{'||word[i]=='}')
                    symobl[j++]=word[i];
            mark=Serch(symobl);
            if(mark==1)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }