3.1栈的应用—括号匹配

一、实验目的    1．掌握堆栈特殊线性表的存储方式的基本操作方法。

2．掌握堆栈后进先出运算原则在解决实际问题中的应用。

3．掌握使用栈的原理来解决表达式中的括号配对问题。

二、实验内容

 假设一个算术表达式中包含圆括弧、方括弧三种类型的括弧，编写一个程序用于判别表达式中括弧是否正确配对。

说明：检验表达式中的括号匹配情况：假设在一个算术表达式中，可以包含三种括号：圆括号"（"和"）"，方括号"["和"]"，并且这两种括号可以按任意的次序嵌套使用。比如，...[......[...]...]...(...)..。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。

提示：

算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。

（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；

（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；

（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。

算法步骤：扫描表达式，

1）凡出现左括弧，则进栈；

2）凡出现右括弧，首先检查栈是否空。

   若栈空，则表明该“右括弧”多余

   否则和栈顶元素比较，

       若相匹配，则“左括弧出栈”

       否则表明不匹配

3）表达式检验结束时，

   若栈空，则表明表达式中匹配正确

   否则表明“左括弧”有余

栈的类型定义及基本操作代码可参考教材相关定义和程序。

 

三、实验源代码

 

四、实验结果

算法逻辑根据题目提示来就行了，由于特定题目所以没有对书上的一些代码进行了修改，比如没有在弹出栈顶的时候设置变量保存栈顶，直接下移栈顶指针（因为此题弹出的栈顶并没有用了）

在编写过程中遇到的若干问题：

0、switch函数的具体格式忘记了，以至于报了很多格式上的错误；

1、特别注意switch函数中多处判断的逻辑

2、对于中括号在小括号中间这种情况并没有检测出来并报错（如"（[]）"）,代码还有进一步改进的空间

ps:编译完成后并没有进行多少数据测试，如若有bug还请批评指出！

#include<stdio.h>  
#include<stdlib.h>
#include<malloc.h>
#define  maxsize 100
//封装顺序栈 
typedef struct{char date[maxsize];int top;
}SeqStack,*PSeqStack; 
//初始化空栈
PSeqStack init(){PSeqStack s;s =  (PSeqStack)malloc(sizeof(SeqStack));if(s){s->top = -1;return s;}
}
//判空
int empty(PSeqStack s) {//返回1表示空，返回0表示不空if(s->top==-1)return 1;elsereturn 0;
}
//出栈
int pop(PSeqStack s){//弹出栈顶，将其保存在x里 if(empty(s))return 0;else{//	*x = s->date[s->top]l;s->top--;return 1;} 
}
//取栈顶元素
char getTop(PSeqStack s) {//栈顶存在*x中，成功1，失败0if(empty(s)) return '0';else{//	*x =s->date[s->top];return s->date[s->top];}}
//销毁栈
void destory(PSeqStack *s) {//如果s空，那么不可以freeif(*s){free(*s);*s = NULL;	}}
//入栈
int  push(PSeqStack s,char x){if(s->top==maxsize-1){return 0;//栈满不可入栈 }else{s->top++;s->date[s->top]=x;return 1;}}void judge(PSeqStack s,char str[]){//判空、判满if(!s||s->top==maxsize-1){return ;}int i;for(i=0; str[i]!='\0'; i++)  {  switch(str[i])  {  case '(':  case '[':  push(s, str[i]);  //遇左括号就入栈  break;  case ')':  //若栈空出现一个右括号，则直接returnif(empty(s)){printf("匹配失败");return ;}//栈不空，验证是否匹配 else{if(getTop(s)=='('){pop(s);break;}				else{printf("匹配失败");return ;} } break;case ']':  //若栈空出现一个右括号，则直接returnif(empty(s)){printf("匹配失败");return ;}//栈不空，验证是否匹配 else{if(getTop(s)=='['){pop(s);break;}				else{printf("匹配失败");return ;} } break;  default: break;  }}//结束循环判断栈是否空，空则匹配成功 if(empty(s)){printf("匹配成功");return ;} else{printf("匹配失败");return;} printf("匹配失败");
}void main(){printf("请输入表达式：\n");PSeqStack myS = init();char s[maxsize];gets(s);judge(myS,s);	destory(&myS);
}