浮点型数据算术表达式求值算法研究与实现

杨爱丽

摘要：针对按常规输入即中缀表达式输入格式的算术表达式求值，提出了一种基于栈结构的浮点型数据表达式求值算法。该算法考虑了算符之间的优先级，同时也考虑了字符串形式的浮点数转换成数值的问题，从而解决了程序设计语言中浮点型数据表达式求值的问题。

关键词：表达式求值；栈；算符优先级；浮点型数据

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2018）16-0261-02

1 背景

算术表达式一般由操作数（operand）、运算符（operator）和界限符（delimiter）组成。操作数由数字0～9和小数点构成，运算符通常包括加、减、乘、除和括号，表达式界限符设定为“=”。由此，算术表达式的构成可分成两类符号：操作数和算符，其中算符包含运算符和界限符。对于按常规输入的表达式（即中缀表达式）的求值是程序设计语言编译器中一个最基本的问题，也是栈的一个典型的应用实例。该文利用栈结构，根据算符之间的优先关系，研究并实现了浮点型数据的算术表达式求值算法。

2 算符优先关系的描述与实现

根据表达式的运算规则：先乘除、后加减，同级运算时先左后右，先括号内后括号外。在运算的每一步中，任意两个相继出现的算符θ1和θ2之间的优先关系有以下三种情况：

θ1<θ2：θ1的优先级低于θ2

θ1=θ2：θ1的优先级等于θ2

θ1>θ2：θ1的优先级高于θ2

对于加、减、乘、除、括号和等号，它们之间的优先关系如表1所示，其中，“E”表示错误，即θ1和θ2不可能相继出现。为方便处理，在表达式的前后分别加上一个“=”作为开始和结束符，它的优先级最低。

表1 算符优先关系表

[

θ1 θ2 + - * / （ ） = + > > < < < > > - > > < < < > > * > > > > < > > / > > > > < > > （ < < < < < = E ） > > > > E > > = < < < < < E = ]

由表1，对于相继出现的算符θ1和θ2，它们之间的优先关系可以归纳为以下5种情况：

1）θ1是“+”和“-”时，当θ2是“*”、“/”和“（”时，它们的优先级关系是“<”，其余时候它们之间的优先关系是“>”；

2）θ1是“*”和“/”时，当θ2是“（”时，它们之间的优先级是“<”，其余时候是“>”；

3）θ1是“（”时，当θ2是表达式结束符时，它们之间的优先级关系用“E”表示，其余情况又可以分成两种：当θ2是“）”时，它们之间的优先级是相同的，用“=”表示，θ2是其他字符时，它们之间的优先关系是“<”；

4）θ1是“）”时，当θ2是“（”时，它们之间的优先级关系用“E”表示，θ2是其他字符时，它们之间的优先关系是“>”；

5）θ1是表达式结束符时，当θ2也是表达式结束符时，它们之间的优先级是相同的，用“=”表示，其余情况又可分为两种：当θ2是“）”时，它们之间的优先级关系用“E”表示，θ2是其他字符时，它们之间的优先级关系是“<”。

这5种情况是根据θ1的值来分的，即当θ1的值确定后，再根据θ2的值来判断。由此，利用多分支选择结构可以实现算符之间的优先关系。算法实现如下：

char Precede （char a， char b） //比较算符a，b的优先级

{

char z；

if（（b=='+'）||（b=='-'）||（b=='*'）||（b=='/'）|| （b=='（'）||（b=='）'） ||（b=='='））

switch （a）

{

case '+'：

case '-'：

if（（b=='*'）||（b=='/'）||（b=='（'）） z='<'；

else z='>'； break；

case '*'：

case '/'：

if（b=='（'） z='<'；

else z='>'； break；

case '（'：

if（b=='='） z='E'；

else if（b=='）'） z='='；

else z='<'； break；

case '）'：

if（b=='（'） z='E'；

else z='>'； break；

case '='：

if（b=='='） z='='；

else if（b=='）'） z='E'；

else z='<'； break；

}

else z='E'；

return（z）；

}

3 字符串形式的浮點数转换成数值算法

在表达式求值过程中，若连续读到由数字和小数点构成的字符串形式的浮点数，如“123.45”，则需要将其转换成数值的123.45后再进行处理。采用while循环读取下一个字符并判断该字符是否是'0'～'9'和'.'，若是，则将其转换成数值型，同时，统计小数的位数。若小数位数为0，则可实现多位整数的计算；若小数位数大于0，则实现浮点数的计算。假设字符指针p已指向表达式字符串（下同），转换算法实现如下：

sum=0；

count=0； //统计小数位数

while（*p>='0'&&*p<='9'||*p=='.'）