栈的应用：表达式求值（中缀表达式，后缀表达式，前缀表达式）

1.三种算术表达式

1.中缀表达式

由三个部分组成:操作数、运算符、界限符。
界限符是必不可少的,反映了计算的先后顺序。

规则：运算符在两个操作数中间.

2.后缀表达式

又称为逆波兰表达式。
规则:运算符在两个操作数后面。

3.前缀表达式

又称为波兰表达式。
规则:运算符在两个操作数前面。

2.后缀表达式相关考点

1.中缀表达式转后缀表达式

1.手算方法

①确定中缀表达式中各个运算符的运算顺序
②选择下一个运算符，按照「左操作数 右操作数 运算符」的方式组合成一个新的操作数
③如果还有运算符没被处理，就继续②

2.例题

运算顺序不唯一，因此对应的后缀表达式也不唯一。
为保证手算和机算结果相同，采用“左优先”原则：只要左边的运算符能先计算，就优先算左边的。

3.机算

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
从左到右处理各个元素，直到末尾。可能遇到三种情况:
①遇到操作数。直接加入后缀表达式。
②遇到界限符。遇到“(”直接入栈;遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。
注意:“(”不加入后缀表达式。
③遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，
若碰到“(”或栈空则停止。之后再把当前运算符入栈。
按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

2.后缀表达式求值

1.手算方法

从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数。
注意：两个操作数的左右顺序。

2.机算

①从左往右扫描下一个元素，直到处理完所有元素
②若扫描到操作数则压入栈，并回到①;否则执行③
③若扫描到运算符，则弹出两个栈顶元素（先出栈的是“右操作数”），执行相应运算，运算结果压回栈顶，回到①
若表达式合法，则最后栈中只会留下一个元素，就是最终结果。

3.前缀表达式相关考点

1.中缀表达式转前缀表达式

1.手算方法

①确定中缀表达式中各个运算符的运算顺序
②选择下一个运算符，按照「运算符 左操作数 右操作数」的方式组合成一个新的操作数
③如果还有运算符没被处理，就继续②
“右优先”原则：只要右边的运算符能先计算，就优先算右边的。

2.例题

2.前缀表达式求值

①从右往左扫描下一个元素，直到处理完所有元素
②若扫描到操作数则压入栈，并回到①;否则执行③
③若扫描到运算符，则弹出两个栈顶元素（先出栈的是左操作数），执行相应运算，运算结果压回栈顶，回到①

4.中缀表达式求值

用栈实现中缀表达式的计算:
①初始化两个栈，操作数栈和运算符栈若扫描到操作数，压入操作数栈
②若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈
（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素（先弹出的是右操作数）并执行相应运算，运算结果再压回操作数栈)