数据结构——栈的应用:表达式求值

一个表达式由操作数(亦称运算对象)、操作符(亦称运算符)和分界符组成。

算术表达式三种表示:

中缀(infix)表示

<操作数><操作符><操作数>

前缀(prefix)表示

<操作符><操作数><操作数>

后缀(postfix)表示

<操作数><操作数><操作符>

逆波兰表示法

 逆波兰表示法Reverse Polish notationRPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

逆波兰结构由弗里德里希·鲍尔(Friedrich L. Bauer)和艾兹格·迪科斯彻在1960年代早期提议用于表达式求值,以利用堆栈结构和减少计算机内存访问。逆波兰记法和相应的算法澳大利亚哲学家计算机学家查尔斯·汉布林(Charles Hamblin)在1960年代中期扩充[1][2]

在1960和1970年代,逆波兰记法广泛地被用于台式计算器,因此也在普通公众(工程商业金融领域)中使用。

下面大部分是关于二元运算,一个一元运算使用逆波兰记法的例子是阶乘的记法。

解释

逆波兰记法中,操作符置于操作数的后面。例如表达“三加四”时,写作“3 4 +”,而不是“3 + 4”。如果有多个操作符,操作符置于第二个操作数的后面,所以常规中缀记法的“3 – 4 + 5”在逆波兰记法中写作“3 4 – 5 +”:先3减去4,再加上5。使用逆波兰记法的一个好处是不需要使用括号。例如中缀记法中“3 – 4 * 5”与“(3 – 4)*5”不相同,但后缀记法中前者写做“3 4 5 * -”,无歧义地表示“3 (4 5 *) −”;后者写做“3 4 – 5 *”。

逆波兰表达式的解释器一般是基于堆栈的。解释过程一般是:操作数入栈;遇到操作符时,操作数出栈,求值,将结果入栈;当一遍后,栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现,和能很快求值。

注意:逆波兰记法并不是简单的波兰表达式的反转。因为对于不满足交换律的操作符,它的操作数写法仍然是常规顺序,如,波兰记法“/ 6 3”的逆波兰记法是“6 3 /”而不是“3 6 /”;数字的数位写法也是常规顺序。

与中缀记法的转换

艾兹格·迪科斯彻引入了调度场算法,用于将中缀表达式转换为后缀形式。因其操作类似于火车编组场而得名。 大多数操作符优先级解析器(解析器用简单的查表操作即可实现,优先级表由开发者自己定制,在不同的应用场景中,开发者可自由改变操作符的优先级)能转换为处理后缀表达式,实际中,一般构造抽象语法树,树的后序遍历即为逆波兰记法。

 

算法

中缀表达式转后缀表达式的方法:

  • 1.遇到操作数:直接输出(添加到后缀表达式中)
  • 2.栈为空时,遇到运算符,直接入栈
  • 3.遇到左括号:将其入栈
  • 4.遇到右括号:执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出。
  • 5.遇到其他运算符:加减乘除:弹出所有优先级大于或者等于该运算符的栈顶元素,然后将该运算符入栈
  • 6.最终将栈中的元素依次出栈,输出。

例如
a+b*c+(d*e+f)*g —-> abc*+de*f+g*+

遇到a:直接输出:
后缀表达式:a
堆栈:空

遇到+:堆栈:空,所以+入栈
后缀表达式:a
堆栈:+
遇到b: 直接输出
后缀表达式:ab
堆栈:+
遇到*:堆栈非空,但是+的优先级不高于*,所以*入栈
后缀表达式: ab
堆栈:*+
遇到c:直接输出
后缀表达式:abc
堆栈:*+
遇到+:堆栈非空,堆栈中的*优先级大于+,输出并出栈,堆栈中的+优先级等于+,输出并出栈,然后再将该运算符(+)入栈
后缀表达式:abc*+
堆栈:+
遇到(:直接入栈
后缀表达式:abc*+
堆栈:(+
遇到d:输出
后缀表达式:abc*+d
堆栈:(+
遇到*:堆栈非空,堆栈中的(优先级小于*,所以不出栈
后缀表达式:abc*+d
堆栈:*(+
遇到e:输出
后缀表达式:abc*+de
堆栈:*(+
遇到+:由于*的优先级大于+,输出并出栈,但是(的优先级低于+,所以将*出栈,+入栈
后缀表达式:abc*+de*
堆栈:+(+
遇到f:输出
后缀表达式:abc*+de*f
堆栈:+(+
遇到):执行出栈并输出元素,直到弹出左括号,所括号不输出
后缀表达式:abc*+de*f+
堆栈:+
遇到*:堆栈为空,入栈
后缀表达式: abc*+de*f+
堆栈:*+
遇到g:输出
后缀表达式:abc*+de*f+g
堆栈:*+
遇到中缀表达式结束:弹出所有的运算符并输出
后缀表达式:abc*+de*f+g*+
堆栈:空

代码:

后缀表达式求值:

  • 顺序扫描后缀表达式每一项。
  • 若该项是操作数则进栈。
  • 若该项是操作符<op>:若是单目运算符,则出栈一个操作数X,并将计算结果<op>X进栈。若是双目运算符,则连续出栈两个操作数X和Y,并将计算结果X<op>Y进栈。(由于操作符的两个操作数也是有左右之分的,操作符左边是第二个出栈的元素,而操作符右边的是第一个出栈的元素。)
  • 当表达式所有项都扫描并处理完后,栈顶存放的就是最后的计算结果。

未经允许不得转载:TacuLee » 数据结构——栈的应用:表达式求值

赞 (0)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址