2022-04-14 括号匹配

#include<iostream>
#include<fstream>
using namespace std;

//顺序栈定义
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE  100//顺序栈存储空间的初始分配量
typedef int Status;
typedef char SElemType;

typedef struct {
    SElemType *base;//栈底指针
    SElemType *top;//栈顶指针
    int stacksize;//栈可用的最大容量
} SqStack;
//算法3.1　顺序栈的初始化
Status InitStack(SqStack &S) {//构造一个空栈S
    S.base = new SElemType[MAXSIZE];//为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
    if (!S.base)
        exit(OVERFLOW); //存储分配失败
    S.top = S.base; //top初始为base，空栈
    S.stacksize = MAXSIZE; //stacksize置为栈的最大容量MAXSIZE
    return OK;
}
//入栈
Status Push(SqStack &S, SElemType e) {  // 插入元素e为新的栈顶元素

    if (S.top - S.base == S.stacksize)
        return ERROR; //栈满
    *(S.top++) = e; //元素e压入栈顶，栈顶指针加1
    return OK;
}
//出栈
Status Pop(SqStack &S, SElemType &e) {  //删除S的栈顶元素，用e返回其值   
    if (S.base == S.top)
        return ERROR;//栈空
    e = *(--S.top); //栈顶指针减1，将栈顶元素赋给e
    return OK;
}
//算法3.4　取顺序栈的栈顶元素
char GetTop(SqStack S) {//返回S的栈顶元素，不修改栈顶指针
    if (S.top != S.base) //栈非空
        return *(S.top - 1); //返回栈顶元素的值，栈顶指针不变
}

Status StackEmpty(SqStack S){
    if (S.top != S.base) //栈非空
    {
        //cout<<"栈非空\n";
        return 0;
    }       
    else
    {
        //cout<<"栈空\n";
        return 1;
    }
}
Status Matching(){
    SqStack S;
    int flag=1;
    InitStack(S);
    SElemType ch,x;
    cin>>ch;
    int count=0;
    while (ch!='#'&&flag) {
        switch (ch) {
        case '(':
        case '[':
        case '{':
            Push(S,ch);     
            break;
        case')':
            if(!StackEmpty(S)&&GetTop(S)=='(')
                Pop(S,x);
            else flag=0;
            break;
        case']':
            if(!StackEmpty(S)&&GetTop(S)=='[')
                Pop(S,x);
            else flag=0;
            break;
        case'}':
            if(!StackEmpty(S)&&GetTop(S)=='{')
                Pop(S,x);
            else flag=0;
            break;
        }
        //count++;
        cin>>ch;
    }
    if(StackEmpty(S)&&flag)
        return true;
    else 
        return false;
}
int main() {
    SqStack S;
    int a=0; 

    cout<<"输入不同的括号，以#结束：";
    if(Matching())
        cout<<"匹配成功\n";
    else 
        cout<<"匹配失败\n";/**/
/*
    do{
        cout<<"输入不同的括号，以#结束：";
        if(Matching())
            cout<<"匹配成功\n\n";
        else 
            cout<<"匹配失败\n\n";
        system("pause");
        cout<<"是否继续 1.继续 0.结束:";
        cin>>a;
    }while(a);
    */
    return 0;
}

测试数据
([]{})#
{[}]#
{{}#
())#