【数据结构】三、栈和队列：4.栈的应用（括号匹配，四则运算表达式求值，进制转换，递归）

文章目录

栈的应用
- 1.括号匹配
- - 1.1三种错误情况
  - 1.2流程图
  - ❗1.3算法c实例
- ❗2.表达式求值
- - 2.1表达式求值
  - 2.2中缀转后缀（手算）
  - 2.3后缀表达式计算
  - 2.4中缀转前缀
  - 2.5中缀转后缀（机算）
  - 2.5表达式树与逆波兰表达式
- 3.进制转换
- 4.递归
- - 缺点

栈的应用

1.括号匹配

判断括号是否是两两匹配的。

遇到左括号就入栈。遇到右括号就出栈一个左括号。

请添加图片描述

1.1三种错误情况

匹配失败：

请添加图片描述

空栈：

请添加图片描述

最后栈非空：
请添加图片描述

1.2流程图

请添加图片描述

❗1.3算法c实例

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MaxSize 50 //定义栈中元素最大个数
typedef char ElemType;		//定义栈中元素类型为chartypedef struct{char data[MaxSize];int top;
}SqStack;void InitStack(SqStack &S);
bool StackEmpty(SqStack S);
bool StackFull(SqStack S);
void Push(SqStack &S,ElemType x);
void Pop(SqStack &S,ElemType *x);//匹配算法
bool bracketCheck(ElemType str[], int length){SqStack 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)){ return false; //匹配失败}ElemType topElem; //用来保存弹出栈的栈顶元素Pop(S, &topElem); //栈顶元素出栈if(str[i]==')' && topElem!='('){return false;}if(str[i]=='}' && topElem!='{'){return false;}if(str[i]==']' && topElem!='['){return false;}}}//扫描完整个字符串，如果栈不为空，说明左括号单身return StackEmpty(S);
}int main(){char str[MaxSize];printf("请输入需要判断的括号：\n");scanf("%s",str);int len = strlen(str);printf("当前输入的括号个数为：%d\n",len);printf("--------现在开始进行判断--------\n");if(bracketCheck(str,len)){printf("匹配成功！");}else{printf("匹配失败！");}return 0;
}//初始化栈
void InitStack(SqStack& S){S.top = -1;
}//判断栈是否为空
bool StackEmpty(SqStack S){if(S.top == -1){return true;}return false;
}//判断栈满
bool StackFull(SqStack S){if (S.top == MaxSize-1)   //top的位置值等于MaxSize-1时栈满,因为是从0开始的return true; elsereturn false; 
}//入栈
void Push(SqStack &S,ElemType x){if(StackFull(S)){printf("栈已满"); //栈已满return;}S.top += 1;S.data[S.top] = x;
}//出栈，用x返回
void Pop(SqStack &S,ElemType *x){if(StackEmpty(S)){printf("栈为空");return;}*x = S.data[S.top];S.top -= 1;
}

❗2.表达式求值

三种算术表达式：
- 中缀表达式
- 后缀表达式
- 前缀表达式
❗后缀表达式の考点
- 中缀表达式转后缀表达式
- 后缀表达式求值
前缀表达式の考点
- 中缀表达式转前缀表达式
- 前缀表达式求值

算术表达式由三部分组成：操作数、运算符、界限符。
$(1 + 2) \times 4$

操作数（运算数）：就是1、2、4这些进行运算的数字
运算符：就是+、×这些运算
界限符：就是符号()这种进行运算顺序的限制。
反应运算的运算顺序。

而不用界限符也能无歧义地表达运算顺序，那就有：

Reverse Polish notation (逆波兰表达式 = 后缀表达式)
Polish notation (波兰表达式=前缀表达式)

中缀表达式	后缀表达式	前缀表达式
运算符在两个操作数中间	运算符在两个操作数后面	运算符在两个操作数前面
a+b	ab+	+ab
a+b-c	ab+c-	-+abc
a+b-c（先算b-c）	a bc- +	+ a -bc
a+b-c*b	ab+ cd* -	- +ab *cd

2.1表达式求值

表达式求值要解决的问题一般是输入一个字符串表示的表达式，要求输出它的值。当然也有变种比如表达式中是否包含括号，指数运算，含多少变量，判断多个表达式是否等价，等等。

表达式一般需要先进行语法分析（grammer parsing）再求值，也可以边分析边求值，语法分析的作用是检查输入的字符串是否是一个合法的表达式，一般使用语法分析器（parser）解决。

表达式包含两类字符：运算数和运算符。对于长度为 n 的表达式，借助合适的分析方法，可以在 O(n) 的时间复杂度内完成分析与求值。

2.2中缀转后缀（手算）

中缀转后缀的手算方法：

确定中缀表达式中各个运算符的运算顺序。
选择下一个运算符,按照「左操作数，右操作数，运算符」的方式组合成一个新的操作数。
如果还有运算符没被处理，就继续步骤②

一个中缀表达式中的运算，在逻辑上有多种顺序（运算顺序不唯一），但是在后缀表达式中只有一种表示。

请添加图片描述

所以，在算法中想要验证（手算）是否正确，只能使用前面的那种后缀表达式逻辑。（保证算法的确定性）

所以，在中缀转后缀中，要采用**“左优先”原则**：只要左边的运算符能先运算，那么就先优先计算左边的。

要注意下面这个例题：

A+B可以在不干扰 * / 运算的情况下，先运算，所有算是左边能先运算的运算符。
$A+B-C*D/E+F\\ ↓\\ AB+ CD*E/ - F+$

2.3后缀表达式计算

手算：从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数。

请添加图片描述

机算：

从左往右扫描下一个元素，直到处理完所有元素。
若扫描到操作数则压入栈,并回到①；否则执行③。
若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①。

2.4中缀转前缀

中缀转前缀的手算方法：

确定中缀表达式中各个运算符的运算顺序。
选择下一个运算符，按照「运算符，左操作数，右操作数」的方式组合成一个新的操作数。
如果还有运算符没被处理，就继续②右边

“右优先”原则：只要右边的运算符能先计算，就优先算的。
$A+B*(C-D)-E/F\\ ↓\\ +A- *B -CD /EF$

2.5中缀转后缀（机算）

3.3.2_栈在表达式求值中的应用(下)_哔哩哔哩_bilibili

中缀转后缀表达式的机算方法：

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。

从左到右处理各个元素，直到末尾。可能遇到三种情况：

遇到操作数。直接加入后缀表达式。
遇到界限符。
1. 遇到(直接入栈；
2. 遇到)则依次弹出栈内运算符并加入后缀表达式，直到弹出(为止。
注意：(不加入后缀表达式。
遇到运算符。
1. 依次弹出栈中已存在的优先级高于或等于当前运算符的所有运算符，并加入后缀表达式；
2. 若碰到(或栈空则停止。之后再把当前运算符入栈。

按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

最后：

通过中缀表达式转后缀表达式的机算方法、后缀表达式的计算，这两种方式的结合，可以直接对中缀表达式进行运算，判断完一个运算符的优先性之后，直接进行运算。

2.5表达式树与逆波兰表达式

一种递归分析表达式的方法是，将表达式当成普通的语法规则进行分析，分析后拆分成如图所示的表达式树，然后在树结构上自底向上进行运算。

对这棵表达式树进行的：

前序遍历 --> 前缀表达式

中序遍历 --> 中缀表达式（需要加界限符）

后序遍历 --> 后缀表达式

3.进制转换

对十进制数进行取余之后放入栈中，再出栈（倒序）就是目标结果。

#include<iostream>
#include<Windows.h>
using namespace std;#define MaxSize 100				//栈最大可以存放的元素个数
typedef char ElemType;		//顺序栈存储的数据类型、代替ElemType//创建顺序栈typedef struct
{ElemType* base;  //栈底指针int top;		 //栈顶的位置 如 0、1、2、3、4....MaxSize
} SqStack;			 //顺序栈的结构体定义bool InitStack(SqStack& stack);	//初始化栈
bool StackEmpty(SqStack stack);//判断是否为空
bool StackFull(SqStack stack);	//判断是否已满
int GetStackSize(SqStack& stack);//获取顺序栈中元素个数bool Push(SqStack& stack, ElemType value);//入栈
bool Pop(SqStack& stack, ElemType& value);//出栈
bool Pop(SqStack& stack);				//出栈重载
bool GetTop(SqStack& stack, ElemType& value);//获取栈顶的元素
void DestroyStack(SqStack& stack);//销毁栈、释放栈的内存//初始化顺序栈
bool InitStack(SqStack& stack){//注意:这里使用new进行空间分配,所以在后面摧毁栈的时候需要delete释放空间//动态分配一个ElemType类型MaxSize长度的空间，将地址给顺序栈Stack的栈底指针stack.base = new ElemType[MaxSize];//判断顺序栈的栈底指针(stack.base)是否为空，若无地址，则分配失败if(!stack.base){return false; }stack.top = -1;		//初始化栈顶指针的位置为-1return true;
}//判断栈空
bool StackEmpty(SqStack stack){if (stack.top == -1)return true;elsereturn false; 
}//判断栈满
bool StackFull(SqStack stack){if (stack.top == MaxSize-1)   //top的位置值等于MaxSize-1时栈满,因为是从0开始的return true; elsereturn false; 
}//顺序栈中元素个数
int GetStackSize(SqStack& stack){return stack.top+1;  //栈顶位置即top的数值，就是栈中元素的个数
}/*** @brief 顺序栈入栈:* 开辟一个新的空间,栈顶+1,然后将数据存入stack.base[stack.top]所在的位置.* * @param stack * @param value * @return true * @return false */
bool Push(SqStack& stack, ElemType value){if (StackFull(stack)){cout<<"栈满"<<endl;return false;  }//若栈未满，执行入栈操作stack.top++;		//栈顶自增1stack.base[stack.top] = value;    //以栈顶位置作为下标存储数据return true;
}/*** @brief 顺序栈出栈:* 读取栈顶stack.base[stack.top]的元素,然后使栈顶-1.* * @param stack * @param value * @return true * @return false */
bool Pop(SqStack& stack, ElemType &value){if (StackEmpty(stack)){cout<<"栈为空"<<endl;return false;}value = stack.base[stack.top];	//以栈顶位置作为下标的值赋值给value返回stack.top--;	//栈顶自减1return true;
}// 重载
bool Pop(SqStack& stack){if (StackEmpty(stack)){cout<<"栈为空"<<endl;return false;}stack.top--;	//栈顶自减1return true;
}//读取栈顶元素
bool GetTop(SqStack& stack, ElemType &value){if (StackEmpty(stack)){cout<<"栈为空"<<endl;return false; }value = stack.base[stack.top];return true; 
}//销毁栈、释放栈的内存
void DestroyStack(SqStack& stack){if(stack.base) {			//若栈底指针分配有地址,则释放delete stack.base;	//释放栈底指针的地址stack.top = -1;			//令栈顶位置为0stack.base = NULL;	//将栈底指针指向空cout<<"栈已释放内存！"<<endl; }
}//-------------------------------------------------------------------------------
// 十进制 -> 二进制
void DTB(int num, SqStack& Stack)
{char num_b[64];   //用来存放转换出来的二进制int i = 0;while(num) {                //2进制，入栈// ！！！注意：将余数转化为字符，用 +'0'Push(Stack, num%2+'0');    //余数放入栈num /= 2;}while(!StackEmpty(Stack)) { //出栈，直到栈为空  Pop(Stack, num_b[i++]);}cout<<"该数对应的二进制数为："<<num_b<<endl;
}// 八进制
void DTO(int num, SqStack& Stack)
{char num_o[32];  //用来存放转换出来的八进制char* temp = num_o;while(num) {        //入栈Push(Stack, num%8+'0');num /= 8;}while(!StackEmpty(Stack)) {   //出栈 直到栈为空  Pop(Stack, *temp);temp++;     //下一个位置}*temp = '\0';printf("该数对应的八进制数为：%s\n",num_o);
}// 十六进制
void DTH(int num, SqStack& Stack)
{char num_h[12] ;  //用来存放转换出来的16进制char* temp = num_h;char top_num;while(num)  //入栈{Push(Stack,num%16);num /= 16;}while(!StackEmpty(Stack))   //出栈 直到栈为空  {Pop(Stack, top_num);if((int)top_num > 9)*temp = top_num - 10 + 'A';else *temp = top_num + '0';temp++; }*temp = '\0';printf("该数对应的十六进制数为：%s\n",num_h);
}int main()
{SqStack	stack;		//创建顺序栈InitStack(stack);	//初始化顺序栈int value = 12;DTB(value,stack);DTO(value,stack);DTH(value,stack);//释放栈的内存DestroyStack(stack);system("pause");return 0;
}

4.递归

函数调用的特点：最后被调用的函数最先执行结束(LIFO)

函数调用时，需要用一个栈，存储：

调用返回地址
实参
局部变量

适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题。

递归调用时，函数调用栈可称为“递归工作栈”。

每进入一层递归，就将递归调用所需信息压入栈顶。每退出一层递归，就从栈顶弹出相应信息。

缺点

递归运算越多，空间复杂度越高。太多层递归可能会导致栈溢出。
效率低。可能包含很多重复计算。

解决办法：

可以自定义栈，将递归算法改成非递归算法。
可以使用带备忘录（memo）的递归（动态规划）。