欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

栈的应用—括号匹配

程序员文章站 2022-07-14 23:13:48
...

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);
}


相关标签: 数据结构