数据结构【一】：前缀表达式与后缀表达式的区别

在早期计息机系统中，由于没有括号规定运算顺序，因此，依靠出栈和入栈两种方式，限定元素和符号之间的关系确定了前缀表达式和后缀表达式两种运算方式，中缀表达式即为普通的运算表达式；注意，在栈结构进行数据删除和增加的一端称之为栈顶Top。

1）前缀表达式（前序表达式、波兰式）
前缀表达式是指不包含括号，将运算符放在两个运算对象前面。中缀表达式转换成前缀表达式时，先确定计算顺序，随后从最里面的一层括号进行转换。原则上从右向左遍历表达式，先将整数从右至左入栈，运算符从左向右入栈。

# 将 1 + ((2 + 3)* 4 ) – 6 表达式转换成前缀表达式,前缀表达式从右往左扫描;
1) (2+3)*4  ===>  * + 2 3 4
2) 1+((2+3)*4) ===>  + 1 * + 2 3 4
3) 1 + ((2 + 3)* 4 ) – 6 ===> - 6 + 1 * + 2 3 4

计算前缀表达式（将前缀表达式转换成中缀表达式） 从右往左遍历前缀表达式
从右往左遍历前缀表达式的字符串，当字符串的字符为变量或整数时，将其压入栈中；当遇到运算符，则将栈顶的两个元素弹出栈外进行运算，将栈顶第1个元素记为top1，栈顶的第2的元素记为top2，
注意：计算方式为 top2 运算符 top1 = 值
运算结束后将结果压入栈中，继续遍历字符串，直到前缀表达式的最左端，最后运算得出的值为该前缀表达式的结果。

# 将前缀表达式转换为中缀表达式 - 6 + 1 * + 2 3 4, 假设栈底为左侧;
1) 从右往左遍历前缀表达式, 栈内数值为 4,3,2
2) 当遇到运算符 + 时,将栈顶的top1元素2和 top2元素3进行运算,即3+2=5,将计算结果入栈,则栈内数据为4,5
3) 当遇到运算符 * 时,将栈顶的top1元素5和 top2元素4进行运算,即4+5=20,将计算结果入栈,则栈内数据为20
4) 当遇到整数1时,加入到栈中,则栈内数据为20,1
5) 当遇到运算符 + 时,将栈顶的top1元素1和 top2元素20进行运算,即20+1=21,将计算结果入栈,则栈内数据为21
6) 当遇到整数6时,加入到栈中,则栈内数据为21,6
7) 当遇到运算符 - 时,将栈顶的top1元素6和 top2元素21进行运算,即21-6=15,将计算结果入栈,则栈内数据为15

2）后缀表达式（逆波兰式）
后缀缀表达式是指不包含括号，将运算符放在两个运算对象后面。中缀表达式转换成前缀表达式时，先确定计算顺序，随后从最里面的一层括号进行转换。原则上从左向右遍历表达式，先将最简表达式整数从左至右入栈，运算符随后入栈。

# 将 1 + ((2 + 3)* 4 ) – 6 表达式转换成后缀表达式
1) (2+3)*4  ===> 2 3 + 4 *
2) 1 + ((2 + 3)* 4 ) ===> 1 2 3 + 4 * +
3) 1 + ((2 + 3)* 4 ) – 5 ===> 1 2 3 + 4 * + 6 -

计算后缀表达式，从左往右遍历后缀表达式
从左往右遍历前缀表达式的字符串，当字符串的字符为变量或整数时，将其压入栈中；当遇到运算符，则将栈顶的两个元素弹出栈外进行运算，将栈顶第1个元素记为top1，栈顶的第2的元素记为top2，
注意：计算方式为 top2 运算符 top1 = 值
运算结束后将结果压入栈中，继续遍历字符串，直到前缀表达式的最右端，最后运算得出的值为该前缀表达式的结果。

# 将后缀表达式转换成中缀表达式  1 2 3 + 4 * + 6 - ,假设栈底为左侧;
1) 从左遍历后缀表达式, 在运算符前面的所有整数入栈 即：1,2,3
2) 遇到运算符 + , 则将栈中 top1 元素3 和 top2 元素2 进行计算, 2+3=5, 同时将结果加入到栈中, 即:1,5
3) 遇到整数4, 加入到栈中, 则： 1,5,4
3) 遇到运算符 * , 则将栈中 top1 元素4 和top2元素5 进行计算, 5*4=20, 同时将结果加入到栈中, 即：1,20
4) 遇到运算符 + , 则将栈中 top1 元素20 和top2元素1进行计算, 1+20=21, 同时将结果加入到栈中, 即：21 
5) 遇到整数6, 加入到栈中, 则: 21 6
6) 遇到运算符 - , 则将栈中top1元素6和top2元素21进行计算,21-6=15