堆栈——括号匹配求解实现

  • Post author:
  • Post category:其他


1.内容和要求

内容:编写程序,使用堆栈实现括号匹配求解。

要求:

1 ) 用户从屏幕输入连续的括号(大中小括号都有),读入括号;

2 ) 编程使用堆栈实现括号是否匹配判断。

2.解决方案

本程序可设置“期待的急迫程度”来说明括号匹配的消除顺序。左括号期待与之匹配的右括号的出现,期待的急迫程度取决于出现的时间先后顺序,后出现的则为最急迫的,这符合栈的“LIFO”特性。故在算法中设置一个栈,每读入一个括号,若是右括号,则或者使置于栈顶的最急迫的期待得以消解,或者是不合法的情况;若是左括号,则作为一个新的更为急迫的期待压入栈中,自然使原有的在栈中的所有未消解的急迫性降低一级。

需要注意的是,在算法开始和结束时,栈都应该是空的。

//检验匹配函数
void BrackCheck(){
    //从终端接受连续的括号,使用字符栈S实现括号是否匹配判断
    SqStack S;
    InitStack(S);           //初始化栈S

    SElemType ch[100];
    cout<<"请输入带括号如()、[]、{}的字符串: "<<endl;
    cin.getline(ch,101,'\n');
    
    SElemType *p,q;
    p = ch;
    while(*p != '\0'){
        switch(*p){
            case '(':
            case '[':
            case '{':
                Push(S,*p++);       //当为左括号时,字符串进栈同时指针p指向下一个字符
                break;
            case ')':
            case ']':
            case '}':
                if(!StackEmpty(S)){ //栈非空
                    Pop(S,q);       //当为右括号时,字符串出栈,返回字符q
                    if(!(q=='('&& *p==')' || q=='['&& *p==']' || q=='{'&& *p=='}')){
                        cout<<"右括号不匹配"<<endl;
                        return;
                    }
                }
                else{   //栈空
                    cout<<"缺少左括号"<<endl;
                    return;
                }
                default:
                    p++;
                    break;
        }//switch
    }//while
    if(StackEmpty(S)){  //栈空
        cout<<"括号完全匹配"<<endl;
    }
    else{               //栈非空
        cout<<"缺少右括号"<<endl;
    }
    DestroyStack(S);    //销毁栈S
}//Brackcheck

3.总结与改进

3.1总结

本程序利用栈结构具有后进先出的特性对括号进行匹配,关键在于括号何时压栈和出栈。故在除了对栈结构基本操作如栈的初始化、判断栈的空与否、压栈与出栈的操作的具体实现,还涉及对缓冲区字符串的字符进出栈的操作问题。只有左括号才进栈,其他字符均可能对左括号出栈构成影响,故使用switch语句加以分类。同时需要注意的是程序前后的空需要为空,即考虑右括号不匹配的情况。

3.2改进

在编写测试函数的过程中,在switch语句里面使用exit(ERROR)来作为不能匹配时退出的语句,但是由于main函数里面使用到do … while()语句,以达到循环测试的效果,可exit(ERROR)语句会导致整个进程或者是整个程序结束。改用return语句后,即可实现结束子函数的进程返回主调函数即main函数。如果不考虑循环测试的情况,eixt(ERROR)与return对于本程序的逻辑均为正确。

同时在main函数中使用getchar()来清除缓冲区的换行符,以保证程序重新进入BrackCheck()的cin.getline,从而保证程序的实用性和鲁棒性。

注:return 是语言级别的,它表示了调用堆栈的返回,用于结束一个函数的执行;而 exit 是系统调用级别的,它表示了一个进程的结束,即退出应用程序.

具体参见链接:

https://blog.csdn.net/qq_29350001/article/details/53096908

4.附录

#include<iostream>

using namespace std;

//预定义变量和类型
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
#define STACKINCREMENT 10

//函数结果状态代码
typedef int Status;         //返回值类型
typedef char SElemType;     //栈的元素类型

typedef struct{
    //顺序栈的表示
    SElemType *base;    //栈构造之前和销毁之后,base的值为NULL
    SElemType *top;     //栈顶指针
    int stacksize;      //当前已分配的存储空间,以元素为单位
}SqStack;

Status InitStack(SqStack &S) {
    //构造一个空栈S
    S.base = new SElemType[MAXSIZE];
    // S.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType));
    if(!S.base) exit(OVERFLOW);
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}//InitStack

Status DestroyStack(SqStack &S){
    //销毁栈S
    delete S.base;
    S.base = NULL;
    S.top = NULL;
    return OK;
}//DestroyStack

Status StackLength(SqStack S){
    //返回栈的长度,即元素个数
    return S.top-S.base;
}//StackLength

Status GetTop(SqStack S,SElemType &e){
    //若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
    if(S.top == S.base) return ERROR;
    e = *(S.top-1);
    return OK;
}//GetTop

Status Push(SqStack &S,SElemType e){
    //插入元素e为新的栈顶元素
    if(S.top-S.base >= S.stacksize){
        S.base = (SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
        if(!S.base) exit(OVERFLOW); //存储分配失败
        S.top = S.base+S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
}//Push

Status Pop(SqStack &S,SElemType &e){
    //若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;
    //否则返回ERROR
    if(S.top == S.base) return ERROR;
    e = *--S.top;
    return OK;
}//Pop

Status StackEmpty(SqStack S){
    //若栈S为空栈,则返回TRUE;否则返回FALSE
    if(S.top == S.base) return TRUE;
    return FALSE;
}//StackEmpty

void BrackCheck(){
    //从终端接受连续的括号,使用字符栈S实现括号是否匹配判断
    SqStack S;
    InitStack(S);           //初始化栈S

    SElemType ch[100];
    cout<<"请输入带括号如()、[]、{}的字符串: "<<endl;
    cin.getline(ch,101,'\n');
    
    SElemType *p,q;
    p = ch;
    while(*p != '\0'){
        switch(*p){
            case '(':
            case '[':
            case '{':
                Push(S,*p++);       //当为左括号时,字符串进栈同时指针p指向下一个字符
                break;
            case ')':
            case ']':
            case '}':
                if(!StackEmpty(S)){ //栈非空
                    Pop(S,q);       //当为右括号时,字符串出栈,返回字符q
                    if(!(q=='('&& *p==')' || q=='['&& *p==']' || q=='{'&& *p=='}')){
                        cout<<"右括号不匹配"<<endl;
                        return;
                    }
                }
                else{   //栈空
                    cout<<"缺少左括号"<<endl;
                    return;
                }
                default:
                    p++;
                    break;
        }//switch
    }//while
    if(StackEmpty(S)){  //栈空
        cout<<"括号完全匹配"<<endl;
    }
    else{               //栈非空
        cout<<"缺少右括号"<<endl;
    }
    DestroyStack(S);    //销毁栈S
}//Brackcheck

int main(){
    int choice;
    cout<<"—————— 括号 匹配 ——————"<<endl;
    do{
        BrackCheck();
        cout<<"—————— 输入1继续 ——————"<<endl;
        cout<<"—————— 输入0结束 ——————"<<endl;
        cin>>choice;
        getchar();  //清除缓冲区中残留的'\n'
    }while(choice == 1);
    return 0;
}//main



版权声明:本文为weixin_51323768原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。