数据结构 实验三 栈的基本操作与应用

一、实验名称：栈的基本操作与应用

二、实验目的：

1、掌握栈的定义及实现；
2、掌握利用栈求解括号匹配的方法。

三、实验原理：

四、实验仪器：Devc++

五、实验内容与步骤：

假设表达式中允许包含3种括号：圆括号、方括号和大括号。设计一个算法判断表达式中的括号是否正确配对。用顺序栈编程实现。

六、实验代码如下

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXSIZE 30
typedef char SElemType;
 
typedef struct{
    SElemType *base; 
    SElemType *top; 
    int stacksize; 
}SqStack;

int InitStack(SqStack &S){
    S.base=new SElemType[MAXSIZE];
    if (!S.base) exit(1) ;
    S.top=S.base;
    S.stacksize=MAXSIZE;
    return 1;
}

bool Push(SqStack &S,SElemType x){ 
    if(S.top-S.base==S.stacksize) 
        return false; 
    *S.top++=x;
    return true;
}

bool Pop(SqStack &S,SElemType &x){ 
    if(S.top==S.base) 
        return false;
    x=*--S.top;
    return true;
}

bool isempty(SqStack S) { 
    if(S.top==S.base)
        return true; 
    else
        return false;
}

bool check(char *str){
    SqStack S;
    InitStack(S);
    int i=0;
    char e;
    while(str[i]!='\0'){
        switch(str[i]){ 
        case '(':
            Push(S,'(');
            break;
        case '[':
            Push(S,'[');
            break;
        case '{':
            Push(S,'{');
            break; 
        case ')':
            if(!Pop(S,e)){
                printf("右括号多于左括号\n");
                return false;
            }
            else if(e!='('){
                printf("左右括号配对次序不正确\n");
                return false;
            }
            break;
        case ']':
            if(!Pop(S,e)){
                printf("右括号多于左括号\n");
                return false;
            }
            else if(e!='['){
                printf("左右括号配对次序不正确\n");
                return false;
            }
            break;
        case '}':
            if(!Pop(S,e)){
                printf("右括号多于左括号\n");
                return false;
            }
            else if(e!='{'){
                printf("左右括号配对次序不正确\n");
                return false;
            }
            break;
        default:
            break;
        }
        i++;
    }
    if(!isempty(S)){
        printf("左括号多于右括号\n");
        return false;
    }
    else
        return true;
}

int main(void){
    char str[50];
    while(1){
        printf("输入表达式：");
        scanf("%s",str);
        if(check(str))
            printf("匹配成功！\n");
        else 
            printf("匹配失败！\n");
    } 
}

版权属于：晓沉

本文链接：https://moexc.com/code/2022-ds3.html

转载时须注明出处及本声名，除特殊说明，原创内容采用CC BY-NC-SA 4.0进行许可