15、数据结构——栈与队列——表达式求值
前言
这部分考到的概率还是非常大的，但是使用纯文本的形式对本人来说还是很难把这个问题讲述好，建议大家去看看B站王道考研课程的视频讲解部分链接
一、三种表达式
三个部分组成： 操作数、运算符、界限符
后缀表达式（逆波兰表达式）
前缀表达式（逆波兰表达式）
中缀表达式转后缀表达式
使用栈实现计算流程：
20min40s~23min左右
中缀表达式转前缀表达式（略）
使用栈实现计算流程：
28min24s~29min36s
二、中缀表达式转后缀表达式
初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
从左到右处理各个元素，直到末尾。可能遇到三种情况：
①遇到操作数。直接加入后缀表达式。
②遇到界限符。遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意：“(”不加入后缀表达式。
③遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(”或栈空则停止。之后再把当前运算符入栈。
按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。
下面的自己试试：
