“链栈”判断表达式中的括号是否正确配对

刺骨的言语ヽ痛彻心扉 2022-07-28 06:30 155阅读 0赞

问题及代码：

/*       
    * Copyright (c) 2016, 烟台大学计算机与控制工程学院       
    * All rights reserved.       
    * 文件名称：date.cpp                             
    * 作    者：单昕昕                                   
    * 完成日期：2016年3月31日       
    * 版 本 号：v1.0                    
    * 问题描述：假设表达式中允许包含3中括号：圆括号、中括号和大括号。
                设计一个算法采用“链栈”判断表达式中的括号是否正确配对。
    * 程序输入：一个字符串表达式。   
    * 程序输出：括号是否正确配对。  
    */ 
    #include<iostream>
    #include<cstring>
    #include<malloc.h>
    using namespace std;
    
    typedef struct linknode
    {
        char data;
        struct linknode *next;
    }LiStack;
    
    void initStack(LiStack *&s)//初始化
    {
        s=(LiStack *)malloc(sizeof(LiStack));
        s->next=NULL;
    }
    
    void Push(LiStack *&s,char e)//进栈
    {
        LiStack *p;
        p=(LiStack *)malloc(sizeof(LiStack));
        p->data=e;
        p->next=s->next;
        s->next=p;
    }
    
    bool Pop(LiStack *&s,char &e)//出栈
    {
        LiStack *p;
        if(s->next==NULL)
            return false;
        p=s->next;
        e=p->data;
        s->next=p->next;
        free(p);
        return true;
    }
    
    bool GetTop(LiStack *s,char &e)//取栈顶元素
    {
        if(s->next==NULL)
            return false;
        e=s->next->data;
        return true;
    }
    
    bool StackEmpty(LiStack *s)//栈是否为空
    {
        return(s->next==NULL);
    }
    
    void DestroyStack(LiStack *&s)//销毁栈
    {
        LiStack *p=s,*q=s->next;
        while(q!=NULL)
        {
            free(p);
            p=q;
            q=p->next;
        }
        free(p);
    }
    
    bool Match(char exp[],int n)//匹配
    {
        int i=0;
        char e;
        bool match=true;
        LiStack *st;
        initStack(st);
        while(i<n&&match)//扫描所有字符
        {//小括号
            if(exp[i]=='(')
                Push(st,exp[i]);//进栈
            else if(exp[i]==')')//若当前为）
            {
                if(GetTop(st,e)==true)
                {
                    if(e!='(')//栈顶不是（时不匹配
                        match=false;
                    else
                        Pop(st,e);//匹配成功出栈
                }
                else match=false;//取不到栈顶元素时不匹配
            }//中括号
            else if(exp[i]=='[')
                Push(st,exp[i]);
            else if(exp[i]==']')
            {
                if(GetTop(st,e)==true)
                {
                    if(e!='[')
                        match=false;
                    else
                        Pop(st,e);
                }
                else match=false;
            }//大括号
            else if(exp[i]=='{')
                Push(st,exp[i]);
            else if(exp[i]=='}')
            {
                if(GetTop(st,e)==true)
                {
                    if(e!='{')
                        match=false;
                    else
                        Pop(st,e);
                }
                else match=false;
            }
            ++i;
        }
        if(!StackEmpty(st)) match=false;//栈不空时表示不匹配
        DestroyStack(st);
        return match;
    }
    int main()
    {
        char s[100];
        cin>>s;
        int len=strlen(s);
        bool m=Match(s,len);
        if(m==true)//匹配成功
            cout<<"SUCCESS!"<<endl;
        else//匹配失败
            cout<<"FAIL!"<<endl;
        return 0;
    }

运行结果：

![Center][]

![Center 1][]

(⊙v⊙)嗯，用栈的进出来做匹配的问题。

我之前还想过能不能直接保存左右括号的数目，因为这个数目一定是相同的，但是后来才发现可能有些情况不成立，比如（））（这种。。

[Center]: /images/20220727/58140ad7613f4842993755c6843782fa.png
[Center 1]: /images/20220727/45f946948efc4c0a91d3b8a6b9436a55.png