数据结构与算法之前缀、中缀、后缀表达式(中缀转前缀、中缀转后缀)
中缀表达式：我们熟悉的算术表达式，如：(3+4)*5-6+8
前缀表达式(波兰表达式)：机器熟悉的算术表达式，如：+ - * + 3 4 5 6 8
后缀表达式(逆波兰表达式)：机器熟悉的算术表达式，如：3 4 + 5 * 6 - 8 +
1. 中缀转前缀语言描述：从右向左遍历中缀表达式，如果是数字就压入数字栈，如果是符号就压入符号栈，如果当前符号比符号栈栈顶符号优先级小则弹出栈顶符号并压入数字栈，如果当前符号比符号栈的栈顶符号优先级大或者相等则压入符号栈，如果有括号，在遍历完括号执行完上述操作以后，括号的符号要依次弹出。依次执行，直到中缀表达式的最后一个元素。然后将符号栈的元素依次弹出压入数字栈，最后依次pop数字栈的元素，取出的结果即为前缀表达式。
2. 中缀转前缀图解描述：
1）
2）
3）
4）
5）
6）
3. 前缀表达式的计算方式文字描述：从右向左遍历表达式遇到数字入栈，遇到符号取出栈顶和次顶数字计算，计算完后再放入栈中。注意栈顶数字为被减数或者被除数
4. 前缀表达式的计算方式画图描述：
1）
2）
3）
4）
5）
5. 中缀转后缀语言描述：从左向右遍历中缀表达式，如果是数字就压入数字栈，如果是符号就压入符号栈，如果当前符号比符号栈栈顶符号优先级小或者相等则弹出栈顶符号并压入数字栈，如果当前符号比符号栈的栈顶符号优先级大则压入符号栈，如果有括号，在遍历完括号执行完上述操作以后，括号的符号要依次弹出。依次执行，直到中缀表达式的最后一个元素。然后将符号栈的元素依次弹出压入数字栈，最后依次pop数字栈的元素，取出的结果即为前缀表达式。
6. 感觉文字描述好啰嗦，直接上图：
1）
2）
3）
4）
5）
6）
7. 后缀表达式计算方式文字描述：从左向右遍历表达式遇到数字入栈，遇到符号取出栈顶和次顶数字计算，计算完后再放入栈中。注意次顶数字为被减数或者被除数
8. 后缀表达式计算方式图片描述：
1）
2）
3）
3）
最后，前缀和中缀表达式的区别：除了遍历顺序不一致之外，符号弹出的条件也不一样，前缀表达式如果当前符号的优先级小于栈顶符号优先级则弹出栈顶符号，而后缀表达式是如果当前符号的优先级小于等于栈顶符号的优先级则弹出栈顶符号，千万不能搞混