栈的应用问题笔记：
栈的应用
/*
栈的应用：括号匹配的检验
假设表达式中包括圆括号和方括号，嵌套随机
例（（））【（）】
给定一串括号表达式，判断括号匹配
思路：
先将左括号push进栈中，然后判断栈顶元素是否与右括号相匹配，匹配则pop栈顶元素
不匹配输出不匹配提示语句，最终栈为空
类似于消消乐，即每一个新来的括号，得与栈顶的左括号相匹配或者作为新的左括号作为栈顶元素被压入
*/
/*
栈的应用：表达式的求值
例：5+6/2-3*4
由两类对象组成（数字和运算符）
不同运算符拥有不同的优先级
中缀表达式：a+b*c-d/e
后缀表达式：abc*+de/-
前缀表达式：a+b*c的写法为+a*bc
处理后缀表达式：
从左到右进行扫描，逐个处理
先push计算数，然后遇到运算符再pop出前两个数进行运算
例：62/3-42*+=
push6,2
pop2,6
came/
push6/2=3
push3
came-
pop3,3
push3-3=0
push4,2
came*
pop2,4
push2*4=8
came+
pop8,0
push8+0=8
考虑到输入问题：中缀表达式-后缀表达式
注意
1.运算数相对顺序不变
2.运算符号顺序发生变化
需要存储运算的符号（Stack）
要将当前运算符和栈顶运算符比较，比较运算符优先级
过程中：
运算数直接输出
左括号压入堆栈
右括号就将栈顶运算符pop并输出，遇到左括号则pop但不输出
运算符优先级大于栈顶运算符，则push
优先级小于栈顶运算符，则pop并输出，再比较，知道运算符优先级大于新的栈顶运算符，push
最终将堆栈内运算符全部输出
*/
/*
栈的应用：汉诺塔问题
64个盘子从小到大依次叠放，需要将其按顺序直接移动到另一个柱子上
要将x柱的盘子借助y柱移动到z柱上
n=1，x-z
n1，将n-1个盘子x-y(借助z),第n个盘子x-z
再将n-1个盘子y-z
*/
//递归代码例程
voidHanoi(intn,charx,chary,charz)
{
if(n==1)
move(x,1,z);
else{
Hanoi(n-1,x,z,y);
move(x,n,z);
Hanoi(n-1,y,x,z);
}
}
//时间复杂度：O(2^n)
/*
递归与栈
判断语句加载递归语句之前
递归的最底层应该有返回值，供上层递归调用
参量初始化在递归开始之前
递归调用需要利用堆栈
*/
/*
迷宫问题
采用“穷举求解”的思路
当前位置（标记）
终点程序结束
非终点四方向中是否存在可通过且未被标记的节点
走到该节点递归
不能通过的地方，需要进行回溯
将上次访问的位置设置为“当前位置”（栈）
typedefstruct{
intord;块的序号
PosTypeseat;块在迷宫中的坐标
intdi;下一个块的方向
}
*/
特别注意：
数据结构课本pdf网盘