栈的应用—括号匹配

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;
	else
		return 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，失败0
	if(empty(s)) 
		return '0';
	else{
	//	*x =s->date[s->top];
		return s->date[s->top];
	}

}
//销毁栈
void destory(PSeqStack *s) {
	//如果s空，那么不可以free
	if(*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 ')':  
        	//若栈空出现一个右括号，则直接return
				if(empty(s)){
					printf("匹配失败");
					return ;
				}
				//栈不空，验证是否匹配 
				else{
					if(getTop(s)=='('){
						pop(s);
						break;
					}				
					else{
						printf("匹配失败");
						return ;
					} 
				} 
				break;
        case ']':  
             //若栈空出现一个右括号，则直接return
				if(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);
}