3.栈和队列的应用

中缀表达式转后缀表达式

算法思想

1. 从左向右开始扫描中缀表达式
2. 遇到数字时,加入后缀表达式
3. 遇到运算符时:
   1. 若为(入栈
   2. 若为),则依次把栈中的运算符加入后缀表达式,直到出现(,从栈中删除(
   3. 若为除括号外的其他运算符,当其优先级高于除(外的栈项运算符时,直接入栈。否则从栈顶开始,依次弹出比当前处理的运算符优先级高和优先级相等的运算符,直到一个比它优先级低的或遇到了一个左括号为止。
4. 当扫描的中缀表达式结束时,栈中的所有运算符依次出栈加入后缀表达式

例子

中缀表达式a/b+(c*d-e*f)/g的转换过程如下:

手工做法

1. 按照运算符的优先级对所有的运算单位加括号，例如上面式子变成((a/b)+(((c*d)-(e*f))/g))
2. 转换为前缀或后缀表达式
   1. 前缀:把运算符号移动到对应的括号前面
   2. 后缀:把运算符号移动到对应的括号后面
3. 把括号去掉