【数据结构】-栈的应用（括号匹配、表达式求值、递归）

ゞ浴缸里的玫瑰 2023-03-01 09:57 4阅读 0赞

### 栈的应用 ###

*  一、写在前面
 *  二、括号匹配
 *   *  1.头文件及类型定义
     *  2.顺序栈类型定义
     *  3.函数声明
     *  4.基本操作
     *   *  4.1 初始化顺序栈
         *  4.2 判空
         *  4.3 入栈
         *  4.4 出栈
         *  4.5 括号匹配逻辑代码
         *  4.6 main函数
 *  三、表达式求值
 *  四、递归
 *   *  1.n的阶乘函数
     *  2.Debug函数调用栈
     *  3.斐波那契函数
     *  4.Debug函数调用栈
     *  5.main函数
 *  五、小结

# 一、写在前面 #

关于接下来介绍的栈的应用，本质上都离不开问题本身都具有**后进先出**的特点，这就是为什么栈可以解决这些问题的原因。

1.  括号匹配  
    \[\]、\{\}、()这三种括号在编写代码时都已经见惯不惯了，如果左括号和右括号不匹配，那么编译器会报错，编译器是怎么知道不匹配的呢，少了左括号？少了右括号？还是左右两个括号本身就不配套。  
    【分析】如果说是这样的一种情况 ‘(((’ ,连续三个左括号，此时来了一个右括号 ‘)’，那这个括号会和上面哪三个括号匹配呢，答案是显然的，会和离他最近的那个括号匹配，但从位置上来说第三个括号是最晚进入的，却最早匹配，即后进先出。
2.  表达式求值  
    关于表达式求值的问题，分很多种情况，将常见的中缀表达式转化为后缀表达式或者前缀表达式之后，利用栈后进先出的特点，按从左到右或者从右到左遍历，将操作数入栈出栈即可，由于具体情况比较复杂，在接下来的图片中，我做了一个总结，此处不再展开。
3.  递归  
    关于递归函数的调用的特点，最后被调用的函数最先执行结束，也利用了栈后进先出的特点。例如：求n的阶乘，会不断调用n-1，到最后n=0或者n=1时的函数执行完成，然后依次返回，最后求出n的阶乘，在这里，n=0或者n=1的函数是最后被调用的，但最先完成，符合后进先出的特点。  
    以上对三个问题的分析仅仅做个引子，主要是介绍问题的共性，都具有后进先出的特点，接下来依次具体介绍。

# 二、括号匹配 #

## 1.头文件及类型定义 ##

#include<stdio.h>
    #include<string.h>
    #define MaxSize 10			//定义栈中元素的最大个数
    #define ElemType char

## 2.顺序栈类型定义 ##

typedef struct {
        
    	ElemType data[MaxSize];		//静态数组存放栈中元素
    	int top;					//栈顶指针,一般来说存放数组的下标
    }SeqStack;

## 3.函数声明 ##

/*函数声明*/
    void InitStack(SeqStack& S);				//1.初始化栈
    bool StackEmpty(SeqStack S);				//2.判空
    bool Push(SeqStack& S, ElemType x);			//3.入栈
    bool Pop(SeqStack& S, ElemType& x);			//4.出栈

## 4.基本操作 ##

### 4.1 初始化顺序栈 ###

//1.初始化栈
    void InitStack(SeqStack& S) {
        
    	S.top = -1;		//初始化栈顶指针为-1
    }

### 4.2 判空 ###

//2.判空
    bool StackEmpty(SeqStack S) {
        
    	return (S.top == -1);
    }

### 4.3 入栈 ###

//3.入栈操作：新元素入栈(先加再存)
    bool Push(SeqStack& S, ElemType x) {
        
    	if (S.top == MaxSize - 1)		//栈满，报错
    		return false;
    	S.data[++S.top] = x;	//栈顶指针+1，栈顶元素入栈
    	return true;
    }

### 4.4 出栈 ###

//4.出栈操作：栈顶元素出栈(先取再减)
    bool Pop(SeqStack& S, ElemType& x) {
        
    	if (S.top == -1)		//栈空，报错
    		return false;
    	x = S.data[S.top--];	//栈顶元素出栈，栈顶指针-1
    	return true;
    }

### 4.5 括号匹配逻辑代码 ###

bool bracketCheck(char str[], int length) {
        
    	SeqStack S;
    	InitStack(S);
    	for (int i = 0; i < length; i++) {
        
    		if (str[i] == '(' || str[i] == '[' || str[i] == '{')
    			Push(S, str[i]);		//扫描到左括号，入栈
    		else {
        
    			if (StackEmpty(S))		//1.扫描到右括号，而且当前栈空，右括号单身，匹配失败
    				return false;
    			char topElem;
    			Pop(S, topElem);		//栈顶元素出栈
    
    			/*2.栈非空，但左右括号不匹配，匹配失败*/
    			if (str[i] == ')' && topElem != '(') 
    				return false;
    			if (str[i] == ']' && topElem != '[') 
    				return false;
    			if (str[i] == '}' && topElem != '{')
    				return false;
    		}
    	}
    	/*
    		3.括号遍历完成
    			若栈非空，左括号单身，匹配失败
    			若栈已空，则匹配成功
    	*/
    	return StackEmpty(S);							
    }

### 4.6 main函数 ###

int main(){
        
    	char s1[] = {
        '(','[','{','}','(',')',']',')'};		//成功匹配
    	char s2[] = {
        '{','[','(',')','}',']','(',')'};		//匹配失败
    	if (bracketCheck(s1, 8))
    		printf("匹配成功!\n");
    	else
    		printf("匹配失败!\n");
    	
    	if (bracketCheck(s2, 8))
    		printf("匹配成功!\n");
    	else
    		printf("匹配失败!\n");
    	return 0;
    }

# 三、表达式求值 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70_pic_center]

# 四、递归 #

## 1.n的阶乘函数 ##

int factorial(int n) {
        
    	if (n == 0 || n == 1)
    		return 1;
    	else
    		return n * factorial(n - 1);
    }

## 2.Debug函数调用栈 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70_pic_center 1]

## 3.斐波那契函数 ##

int Fib(int n) {
        
    	if (n == 0)
    		return 0;
    	else if (n == 1)
    		return 1;
    	else
    		return Fib(n - 1) + Fib(n - 2);
    }

## 4.Debug函数调用栈 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70_pic_center 2]

## 5.main函数 ##

int main() {
        
    
    	int a = factorial(5);
    	printf("%d\n",a);
    
    	int b = Fib(5);
    	printf("%d\n",b);
    
    	return 0;
    }

# 五、小结 #

1.  在括号匹配问题中，使用的是顺序栈，如果存储括号很多，可能会造成栈溢出，可以使用链栈来解决。
2.  关于表达式求值的问题，情况比较复杂，本文仅给出了大概的框架，需要动手画图来理解更为深刻。
3.  函数的递归调用问题中，用到了两个简单的例子，求n的阶乘和斐波那契数列，需要关注的点并不是这两个函数是怎么实现的，主要是理解在函数调用过程中，栈的后进先出。如上图中debug时参数n的变化以及他们在栈中的位置。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/d113f425443f4b4c9b17f5caa69de92b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230209/3b3fae0d169848879d5549ba97ebfb0a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pYX1pYXw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230209/0ac13ab543ad4283b68f805c3765a6e1.png