《数据结构》实验报告（三）——栈的应用（括号匹配）

我会带着你远行 2022-12-23 03:57 225阅读 0赞

## 栈的应用——括号匹配 ##

*注：代码直接从实验报告上复制的，可能格式啥的有错误。*  
**一、实验目的**  
(1) 掌握用C语言调试程序的基本方法。  
(2) 掌握栈的基本定义及其存储实现。  
(3) 掌握栈的常见算法的程序实现。  
(4) 掌握栈在实际问题背景下的灵活应用。  
**二、实验内容**  
算术表达式中右括号和左括号匹配的次序正好符合后到括号要最先被匹配的“后进先出”堆栈操作特点，因此可以借用一个堆栈来进行判断。  
*具体方法：*  
⑴ 顺序扫描算术表达式（表现为一个字符串）；  
⑵ 当遇到三种类型的左括号时，让该括号进栈；  
⑶ 当遇到某一种类型的右括号时，比较当前栈顶括号是否与之匹配，  
⑷ 若匹配则退栈，转（1）继续进行判断；  
⑸ 若不匹配，则左右括号配对次序不正确，结束。  
⑹ 若字符串当前为某一类型的右括号而堆栈为空，则右括号多于左括号，结束。  
⑺ 若字符串扫描结束而堆栈非空，则左括号多于右括号，结束。  
⑻ 若字符串扫描结束而堆栈为空，则左右括号匹配正确，结束。  
**三、实验要求**  
(1) 程序要添加适当的注释，程序的书写要采用缩进格式。  
(2) 程序要具备一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。  
(3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。  
(4) 根据实验报告模板详细书写实验报告（程序调试成功的，需将运行结果截图附在实验报告里面；实验报告以pdf格式或者.doc格式/.docx格式上传）。  
(5) 将源程序(.c或者.cpp)压缩为一个文件（如果自定义了读、写文件则一起压缩）上传，扩展名为：.rar或.zip。  
**四、实验环境**  
Windows 10，Microsoft Visual C++ 2010 Express  
**五、实验代码**

#include<stdio.h>
    #define MAXSIZE 30
    
    typedef struct{
        
    	char data[30]; 
    	int top; 
    }sqstack;
    
    void initstack(sqstack &S){
        
    	S.top=-1;
    }
    
    bool push(sqstack &S,char x){
         
    	if(S.top==MAXSIZE-1) 
    		return false; 
    	S.data[++S.top]=x;
    	return true;
    }
    
    bool pop(sqstack &S,char &x){
         
    	if(S.top==-1) 
    		return false;
    	x=S.data[S.top--]; 
    	return true; 
    }
    
    bool isempty(sqstack S) {
         
    	if(S.top==-1)
    		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;
    }
    
    void main(){
        
    	char str[50];
    	printf("输入表达式：");
    	scanf("%s",str);
    	if(check(str))
    		printf("匹配成功！\n");
    	else 
    		printf("匹配失败！\n");
    }

**六、运行结果**  
![实验结果1][1]  
![实验结果2][2]  
![实验结果3][3]

[1]: /images/20221120/97712b9ce7b246219a77353926be389b.png
[2]: /images/20221120/5b4ecdcc88324d51964ef3d8559e20e6.png
[3]: https://img-blog.csdnimg.cn/20201122160240207.png#pic_center