大话数据结构-4.9 栈的应用——四则运算表达式求值 - 高飞网

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

2016-12-21 15:23:00.0

4.9.1 后缀(逆波兰)表示法定义

已知数学表达式:9+(3-1)×3+10÷2,如何在计算机中对它进行求值?

    这里面的困难就在于乘除在加减后面,却要先运算,而加入了括号,就变得更加复杂,不知道如何处理。

    但仔细观察后发现,括号都是成对出现的,有左括号就一定会有右括号,对于多重括号,最终也是完全嵌套的。这用栈结构正好合适,只要碰到左括号,就将此左括号进栈,不管表达式有多少重括号,反正遇到左括号就进栈,后面出现右括号时,就让栈顶的左括号出栈,期间让数字运算,这样,最终有括号的表达式从左到右巡查一遍,栈应该是由空到有元素,最终再因匹配成功后成为空栈的结果。

    逆波兰(Reverse Polish Notation,RPN)表示:一种不需要括号的后缀表达法。之所以称为后缀表示法,是因为所有的符号都是在要运算数字的后面出现。

    看上面的表达式,转为后缀表达式后:9 3 1 - 3 *+10 2 / +

4.9.2 后缀表达式计算结果   

    规则:从左到右遍历表达式中的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处理栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。

  1. 初始化一个空栈。
  2. 后缀表达式中的前三个都是数字,所以9、3、1依次进栈。
  3. 然后是“-”,所以将栈中的1、3出栈,3-1=2,将2进栈。
  4. 然后是3进栈。
  5. 3后是“*”,2*3=6,将6进栈。
  6. “*”后是“+”,9+6=15,将15进栈。
  7. 10、2依次进栈。
  8. 之后是“/”,10/2=5,将5进栈。
  9. 之后是“+”,15+5=20,将20进栈。
  10. 20出栈,即结果为20。

流程如下图所示:







4.9.3 中缀表达式转后缀表达式

    标准的四则运算表达式,即“9+(3-1)×3+10÷2”叫做中缀表达式

    规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式。

  1. 初始化一空栈。
  2. 第一个数字是9,输出9,之后是“+”,将“+”进栈。
  3. 之后是“(”,将"("进栈。
  4. 之后是数字3,输出。总表达式为 9 3。接着是“-”,进栈。
  5. 之后是数字1,输出,总表达式为 9 3 1。接着是“)”,我们需要去匹配此前的“(”,所以栈顶依次出栈,并输出,直到“(”出栈为止。此时左括号上方只有"-",因此输出“-”。总表达式 9 3 1 -
  6. 接下来是“×”,进栈,然后是3,输出,总表达式为 9 3 1 - 3
  7. 之后是“+”,进栈,“+”之目前栈顶的“*”优先级小,所以将栈中的符号都出栈,总表达式为 9 3 1 - 3 * +。之后将此处的“+”进栈。
  8. 之后是数字10,输出,总表达式为: 9 3 1 - 3 * + 10
  9. 之后是符号“÷”,由于“÷”优先级大于栈顶的“+”,进栈。
  10. 之后是数字2,输出,总表达式为:9 3 1 - 3 * + 10 2
  11. 最后将符号都出栈,总表达式为:9 3 1 - 3 * + 10 2 / +

流程如下图所示:








    从刚才的推导中你会发现,要想让计算机处理我们通常的标准(中缀)表达式的能力,最重要的就是两步:

  1. 将中缀表达式将为后缀表达式(栈用来进出运算的符号)。
  2. 将后缀表达式进行运算得出结果(栈用来进出运算的数字)。
上一篇:第9章 排序
下一篇:4.10 队列的定义 111