如何进行算术表达式的求值

问题:对一个形如“(2!)^(cos(0)+(-2))”的算术表达式求值。

最近《数据结构》课程讲到堆栈的应用,碰到了这个经典的问题:数学表达式的求值。

众所周知,双目运算符有中缀式(自然形式)、前缀式(波兰表达式)、后缀式(逆波兰表达式)三种表示方法,其中后两种易于求值(只需顺序扫描一遍即可)。一种典型的想法是,先把中缀式转换为后缀式(如果利用堆栈,大致是线性时间、线性空间),然后对后缀式求值(线性时间)。

但是这种方法看起来只对二元运算符有效。如果出现了一元运算符,比如 “-1”,这里这个表示一元“取反”运算的负号,需要被转化成 “0-1”,变成二元“减法”运算的减号,方可用前缀式或后缀式求值。除了出现在运算数前面,一元运算符还可以出现在运算数后面,比如阶乘。更甚者,一元运算符可以以“函数”的形式出现,引入更多的括号,比如下式:

(2!)^(cos(0)+(-2))

实际上我们可以认为 f(x),fx,xf 是一元运算符的三种形式。

问题:对一个含有一元运算符、二元运算符、括号的自然形式的算术表达式求值。其中一元运算符的形式包括 “sin(233)”、“-233”、“233!”。

本文将给出一种处理以上问题的有效算法。这一算法在表达式的自身形式上进行迭代,近似具有平方(表达式长度 x 运算符个数)的时间复杂度。可改用栈结构避免重复扫描查找括号,可降低时间复杂度,但将需要线性的额外空间。

1 顺序扫描,查找最内层的一对括号(最靠右的“(”和相应的“)”)

2 查找括号内是否有运算符
    2.1 如果有,对括号内的部分进行求值(子问题)
    2.2 如果没有,检查括号左侧是否有函数名
        2.2.1 如果有,求值
        2.2.2 如果没有,去掉括号

3 重复以上步骤,直到找不到任何括号

其中调用了一个子问题:对不含括号的表达式求值。这时候只有 fx 和 xf 两种形式的一元运算符,且识别起来相当容易:与其他运算符相邻的运算符就是一元运算符。可以先将所有一元运算符求值,然后按正常二元运算符表达式的方法求值。

以下是该算法作用于上例的过程。为避免二义性,以 @ 表示“表示数值的负号”,与运算符“-”区分。

(2!)^(cos(0)+(-2))
(2!)^(cos(0)+(@2))
(2!)^(cos(0)+@2)
(2!)^((1)+@2)
(2!)^(1+@2)
最内层 (1+@2)
最内层 @1
(2!)^(@1)
(2!)^@1
最内层 (2!)
最内层 2
(2)^@1
2^@1
最内层 (2^@1)
最内层 0.5
0.5

以下链接是我(/*于一年前←_←*/)按照该算法写的 C 语言程序,它可以处理前置的一元运算符“-”(取负)、后置的一元运算符“!”(阶乘),可以处理十二种函数 {“cos”,”sin”,”tg”,”ctg”,”abs”,”sign”,”sqrt”,”ln”,”sinh”,”cosh”,”tanh”,”coth”},可以处理五种二元运算符 {‘+’, ‘-‘, ‘*’, ‘/’, ‘^’},可以正确处理括号,同时还实现了一部分大数计算。

https://github.com/lizy14/C-assignments/blob/master/expressionCALC.cpp

(完)