在之前的文章中,我们已经实现了输入一个四则运算表达式(即只包含加减乘除和括号的表达式)的字符串,然后求出其运算结果的功能。整个过程的算法是非常明确,而且并不复杂,包括转换及求值,算法的时间复杂度为O(N),事实上,如果我们在字符一个个读入的时候同时进行转换求值,也是可以的。在实现了四则运算后,这样的程序几乎就可以作为一个比较“智能”的计算器的后台了(这时候我们输入2+3*4,得到的结果不会再是20,而是会得到正确的结果14),但是这样并不能使我们满足,我们所实现的四则运算,实在太简单,而如果想计算更为复杂的表达式,仅仅通过这四种运算,就显得力不从心了。这篇文章,作为解析算术表达式的最后一篇,我想主要来延伸讨论下面几个问题:

1.四则运算属于左结合的运算符,那么对于右结合的运算符,能否很好的加入进来呢?比如“^”这样的幂指运算符(对于习惯C语系的童鞋来说,a ^ b这样的运算等效于pow(a, b)),至于左结合和右结合的区别,稍后会在下文中谈到。
2.能否加入函数运算,让表达式支持sqrt(a+b)+c*d这样带有函数表达式?(sqrt()函数的作用是求自变量的根值)
3.关于预处理,即去掉表达式中多余的空格,对于负数的识别(比如-2*3或者sin(-1))该如何实现

下面,我们就来逐条解决。

1.
关于运算符,主要需要知道的就是三个特征:

1.优先级
2.结合性
3.目

所谓优先级,之前我们已经或多或少了解过了,优先级高的,在运算中应当优先运算。
那么结合性呢?结合性有左结合和右结合之分,对于左结合的运算符,我们以减法为例子:

1 – 2 – 3

所谓左结合,就是遵循从左到右依次计算的规律,也就是

先计算
1 – 2
再计算
– 3

从后缀式中我们可以看出这样的结合性规律,也就是

1, 2, -, 3, –

然而幂指运算符“^”,则属于右结合的运算符,比如给出运算式:

4^3^2

自然书写就是这样:

这个表达式我们应该怎么计算呢?
正确的算法顺序是从右往左看,也就是这个运算式等价于4^(3^2)
同样我们转换为后缀式来看,就应该写成

4, 3, 2, ^, ^

在实际过程中,我们该怎么区别对待这两种不同结合性的运算符呢?
事实上,我们只需要在“比较优先级”的地方做一点改进即可,
对于右结合的运算符,我们遵循同级运算从左到右的顺序,换句话说,一个运算符,进行过一次运算后,再遇到和它同级别的运算的时候,新的运算符优先级要比较低。
用数学语言来模拟这个过程就是:

符号A的优先级 >= 符号B的优先级 –> 符号A的优先级大

也就是说,当A和B运算符同级的时候,认为后一个运算符优先级小。
对于右结合的运算符则是:

符号A的优先级 > 符号B的优先级 -> 符号A的优先级大

同样,这意味着,A和B两个符号同级的时候,认为后一个运算符的优先级大。
这样,我们的改进就非常容易了,具体的代码变动,请参看文章最后附带的完整代码的cmpPRI()函数。
至于运算符的目,就是所谓的与运算符结合的数字的个数,比如阶乘运算5!,这个!只需要一个数字5,就可以进行运算,那么!就是一个单目运算符,而加减乘除,都需要两个数字参与运算,所以它们都是双目运算符。对于不同目的运算符,我们只需要在运算符计算的时候,根据相应的目数,从栈中取出相应数目的数字即可。

2.
其实在四则运算中括号的实现,已经是为我们实现函数计算作了铺垫,我们现在甚至可以认为左括号,是一个什么都不做(输入什么数返回什么数)的函数。恩,说到这了,还有什么疑惑么?
我们可以把左括号,当做一个可以结合各种运算的函数框架,
比如“sin(”,实质上是括号里面的运算完毕后(括号的优先级无可比拟呀!),然后由单目运算符“sin”来完成运算,实质上“sin(”和“*(”在处理上,除了优先级和运算目有所不同外,其它的完全一样。不过对于实际的程序而言,我们需要将字符串转化为程序可以理解的运算符,仅仅是多此一步而已,方便吧?
其实还有更神奇的,增加一个“,”逗号运算符,这个运算符优先级最低最低,以至于必须别的都算完了,才能轮上它,而它在运算过程中什么都不干,就相当于是把和它相邻的两个数字置入数字栈之中,那么加上它又什么用呢?有了这个运算符,我们就可以不加修改的增加“多元函数”的运算,关于这点有点小神奇是吧,哪里会用到多元函数呢?
比如我们定义一个函数

if(a, b, c)

用C代码写其具体实现,就是等价于:

或者干脆是

此函数的if,相当于一个“三目运算符”,在运算的时候会提出数字栈中的三个数字,好玩吧,简简单单,我们就实现了分支结构。

3.
预处理这个东西我犹豫了很长时间。最后由于尝试假如了if函数,导致嵌套多个if函数,或者单个if函数中的表达式较长,那么书写和阅读起来都会比较困难,所以我们需要把表达式中的空格去掉。实际过程中,只要我们读到空格或换行,就跳过不予理睬即可。
至于负数,这是由于负号和减号是同一个运算符,不方便区分,所以通常做法是在负号的前面补一个0:
正确的带负号的表达式应当是这样的:

-3 * 2
2 * (-3)

所谓补零就是:

0 – 3 * 2
2 * (0 – 3)

在算法中,只要我们发现一个减号的前面不是数字,那么就可以认为这个符号是负号,那么就在数字栈中压入一个0即可。
有人提出过这样的问题:

2 * -sin(3)

补零会导致运算错误,实际上按照我们之前的约定,这样的表达式是不合法的,应当写成:

2 * (-sin(3))

实际上预处理过程写出来只用了两行代码。确实是很容易的。

至此,文章也该告一段落了。但是探索的眼睛不应该仅仅局限在文内,其实我给出的代码还有很多值得改进,比如运算符优先级表,能否静态化,不至于每次调用比较优先级都要重构一次表?比如语法错误,符号输入错误的检测,这些错误都会导致程序直接崩溃掉……
解析一个运算表达式可以实现很多很多出色的功能,你甚至可以用这个函数来实现一个简单的脚本代码执行器(我曾经做过一个PHP代码的MCode程序,核心就是一个表达式解析器(比我这个复杂,当然也更为健壮,不过功能都一样),我这个解析器函数实现了类BASIC代码的指令,可以绘制函数图像(甚至于三维的),可以求解线性方程的根)。总之,精彩,是要用脑子创造的!
好了,最后的代码:

 

 

说点什么

2 评论 在 "解析算术表达式[3]扩展与延伸"

提醒
排序:   最新 | 最旧 | 得票最多

[…] 在前一篇文章中我们已经了解到了牛顿迭代法的基本原理,在现在,我们就要将其编写为程序。 为了实现输入一个方程,给出其解的目标,我们需要一个能计算出字符串表达式的结果的函数,这个函数功能我在之前的文章中已经完成了,请参看[这里],在今天的代码中,我们默认Compute函数是已经定义完成的。 首先,我们需要简化我们要解决的问题: 输入一个一元方程,给出解。 对于一元方程而言,只有一个未知数,那么我们目前姑且认为这个未知数的符号就是小写的“x”,实际上我们从[上一篇文章]中就能了解到,我们只用考虑在x的估计值上的函数和导函数的值即刻,也就是说,在处理这个问题的时候,这个方程中的x,只要根据需要被替换为要带入的数值,就可以直接计算了。 方程的形式多种多样,但我们总能将其转化为F(x) = 0的样子,比如f(x) = g(x),只需要把等号改为减号,我们就能得到这个方程的整齐样式,这样我们再带入数值的时候,只需要计算f(x) – g(x)的结果,就可以了。 在处理这个问题上,我们使用的方法很简单: 1.找到等号,替换为“-(” 2.在方程的最后再添加“)” […]

[…] 在下一篇文章中,我将利用之前制作的“表达式解析”,来实现利用计算机求解一元代数方程的程序:)。 Posted In 开发探索 – […]