| 标题 | 浮点型数据算术表达式求值算法研究与实现 |
| 范文 | 杨爱丽 摘要：针对按常规输入即中缀表达式输入格式的算术表达式求值，提出了一种基于栈结构的浮点型数据表达式求值算法。该算法考虑了算符之间的优先级，同时也考虑了字符串形式的浮点数转换成数值的问题，从而解决了程序设计语言中浮点型数据表达式求值的问题。 关键词：表达式求值；栈；算符优先级；浮点型数据 中图分类号：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=='.'） |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。