|||
作者:蒋迅
让我们来看一个简单的例子。这是笔者在工程计算中用到的一个输入文件的一部分,它代表的是一个净化系统的质量的计算公式。
运行时,软件需要先读入这个输入文件,然后计算这个数学表达式并输出答案。要想实现这个计算并不难。用FORTRAN、Java或C,我们可以在源程序里嵌入函数的定义 (以C语言为例):
如果使用MATLAB这样的软件或Python这样的直译式电脑程式语言的话会更方便,用户可以直接把数学表达式输入计算机进行计算。所以我知道很多人觉得这是一个不值得一提的问题。
但我面临的是,输入文件中的参数和数学表达式都是随时可能被用户改变的。这些公式有些是在书 本中理论推导得到的,有些则是工程师们在长期工作中总结出来的经验公式,而且在设计计算中经常会改变。我们不能要求用户每次都重新编写程序或重新汇编软 件。所以,这些表达式及其所用得参数都必须原封不动地由软件读入,然后由软件来解读翻译并计算。这是本文要介绍的重点。
我们从最简单的例子开始。假定我们要求3和5的和。通常的记法是: 3+5。因为计算的算子在两个数之间,我们把它称为“中缀表示法”(infix notation)。
这种表示法有一个缺点,那就是当我们需要计算包括加、减、乘、除、乘方、开方、对数甚至常用 的函数等多种运算的比较复杂的算式时可能会出现混淆。我们必须引入括号来表明计算的顺序。当然大家平时可能并不都用括号,那是因为我们已经默认了“先乘除 后加减”的等规则。问题是我们必须要教计算机也遵循这些规则。于是出现了“前缀表示法”(prefix notation)。用前缀表示法,上面的算式就成了+35。“前缀表示法”是波兰数学家扬·武卡谢维奇 (Jan Lukasiewicz) 1920年代引入的,用于简化命题逻辑。这种算法避免了由于计算顺序所引起的可能麻烦。“前缀表示法”也称为“波兰表示法”。比如“中缀表示法”所表达的(3+5)*4数就可以用“中缀表示法”写成*+354。注意在这个例子里,“中缀表示法”的括号是必需的,如果将括号去掉,我们就得到一个完全不同的数值:3+5*4。
没有理由规定算子必须放在前面。我们也可以把算子放在后面。这样的表示法就是“后缀表示法”(postfix notation)。 因为“后缀表示法”与“前缀表示法”正好顺序相反,所以也叫“逆波兰表示法”(Reverse Polish notation,缩写:RPN)。“后缀表示法”由弗里德里希·鲍尔(Friedrich L. Bauer)和艾兹格·迪科斯彻在1960年代早期提议用于表达式求值,以利用堆栈 (Stack) 结构和减少计算机内存访问。“后缀表示法”和相应的算法由澳大利亚哲学家、计算机学家查尔斯·汉布林(Charles Hamblin)在1960年代中期扩充用“后缀表示法”,我们可以把“中缀表示法”的3+5写成35+;把“中缀表示法”的(3+5)*4写成435+*。
惠普的RPN计算器
理论上说,“后缀表示法”和“前缀表示法”是等价的,但是在实际编程中读取数据上更简洁一些,还可以使用堆栈,所以更受商家喜欢。惠普生产的多种计算器都是用的这种算发。有兴趣的读者可以在维基百科上继续了解后缀表示法。很多数据结构的教科书也都有介绍。这里不再赘述。
Source: Fast Mathematical Expressions Parser
笔者在最后想介绍一款自动读取数学公式的开源软件:“muParser”。这个开源软件是用C++写成的,可以在任何的C++标准编译环境里进行开发。因为开发者提供了源码,使用者可以把它作为静态连结函式库和动态链接库嵌入到自己的程序中。据开发者介绍,muParser有以下优点:
muParser的作者是德国的一位软件工程师:Ingo Berg (iberg)。笔者在网上找不到关于他的任何介绍。但他提供的这个软件包获得了一致好评。推荐与笔者有相同计算需要的读者认真考虑使用muParser。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-26 02:54
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社