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

桃扇骨 2022-07-28 08:35 133阅读 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;
    const int MaxSize=100;
    
    typedef struct linknode
    {
        char data[MaxSize];
        int top;
    }SqStack;
    
    void initStack(SqStack *&s)
    {
        s=(SqStack *)malloc(sizeof(SqStack));
        s->top=-1;
    }
    
    bool Push(SqStack *&s,char e)
    {
        if(s->top==MaxSize-1)
            return false;
        s->top++;
        s->data[s->top]=e;
        return true;
    }
    
    bool Pop(SqStack *&s,char &e)
    {
        if(s->top==-1)
            return false;
        e=s->data[s->top];
        s->top--;
        return true;
    }
    
    bool GetTop(SqStack *s,char &e)
    {
        if(s->top==-1)
            return false;
        e=s->data[s->top];
        return true;
    }
    
    bool StackEmpty(SqStack *s)
    {
        return(s->top==-1);
    }
    
    void DestroyStack(SqStack *&s)
    {
        free(s);
    }
    
    bool Match(char exp[],int n)
    {
        int i=0;
        char e;
        bool match=true;
        SqStack *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][]

[Center]: /images/20220727/5743a3f4bc564c259fb3f380946f260d.png
[Center 1]: /images/20220727/66ce7685339b45f5837df9def2f2cf4c.png