栈的应用: 四则运算表达式求值

例:

9+(3-1)*3+10/2

计算机如何计算这个表达式呢?

人一眼能看出来是20

中缀表达式

标准的四则运算表达式也就是人写出来的,称为中缀表达式,因为所有运算符号在两个数字之间

后缀表达式

将上面的表达式转为后缀表达式:

9 2 3 * + 10 2 / +

(计算机)求四则运算表达式值步骤:

1. 将中缀表达式转为后缀表达式
2. 根据规则计算后缀表达式的值

如何根据后缀表达式求值

原表达式: 9 2 3 * + 10 2 / +

计算过程:

1. 9 2 3 * -> 9 6

2. 9 6 +->15

3. 15 10 ->15 10 2 /->15 5

4. 15 5 + ->20

计算过程

1. 从左到右遍历后缀表达式的每一个数字和字符.遇到数字则入栈,遇到符号,将栈顶两个数字出栈,进行运算,运算结果入栈,
2. 重复上面过程

例子:

计算9 3 10 * - 100 9 3 / - 1 + 2 * + 5 -

1. 9 3 10 *->9 30
2. 9 30 -->-21->-21 100 9 3
3. -21 100 9 3 /->-21 100 3
4. -21 100 3 - -> -21 97
5. -21 97 1 +->-21 98
6. -21 98 2 * -> -21 196 +->175
7. 175 5 -->170

如何将中缀表达式转换为后缀表达式

例如:9+(3-1)*3+10/2

左边是输出,右边表示栈:

9

9 +

9 + (

9 3 + (

9 3 + ( -

9 3 1 + ( - )

9 3 1 - +

9 3 1 - + *

9 3 1 - 3 + *

9 3 1 - 3 + * +

9 3 1 - 3 * + +

9 3 1 - 3 * + 10 + /

9 3 1 - 3 * + 10 2 + /

9 3 1 - 3 * + 10 2 / +

9 3 1 - 3 * + 10 2 / +

转化流程

1. 从左到右扫描中缀表达式.数字直接输出,符号则进行判断

2. 将此符号和栈顶的符号进行比较,如果优先级大于栈顶符号,则入栈,如果此符号是括号直接入栈,是右括号则从栈顶部元素依次出栈并输出,

   不高于的话,则从栈顶开始依次元素依次出栈并输出

3. 重复过程2

上面的第2部分的意思 就是要 保持栈中符号的优先级别是从左到右是严格递增的,

如果当前符号想入栈,并且不能保持此性质,则从栈顶开始的元素依次出栈