数据结构 实验二：算术表达式求值.ppt

《数据结构 实验二：算术表达式求值.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验二算术表达式求值问题描述表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。基本要求以字符序列的形式从键盘输入语法正确的，不含变量的整型表达式。利用教科书表3.1给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例3.1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。算符优先关系矩阵+-*/()#+⋗⋗⋖⋖⋖⋗⋗-⋗⋗⋖⋖⋖⋗⋗*⋗⋗⋗⋗⋖⋗⋗/⋗⋗⋗⋗⋖⋗⋗(⋖⋖⋖⋖⋖≐)⋗⋗⋗⋗⋗⋗#⋖⋖⋖⋖⋖≐测试数据3*(7-2)1+2+3+488-1*51024/4*810

2、24/(4*8)(20+2)*(6/2)2*(6+2*(3+6*(6+6)))(((6+6)*6+3)*2+6)*2实现提示（1）设置运算符栈和运算数栈辅助分析算符优先关系。（2）在读入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理，以及相应的运算。（3）在识别出运算数的同时，要将其字符序列形式转换成整数形式。（4）在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容。选做内容1变算符优先矩阵为算符优先函数：在实际实现算符优先分析算法时，一般不用优先矩阵，而是用两个函数：入栈优先函数f和比较优先函数g。它们如下定义：若θ1⋖θ2则f(θ1)

3、2)若θ1≐θ2则f(θ1)=g(θ2)若θ1⋗θ2则f(θ1)>g(θ2)一种方便地求算符优先函数的方法——迭代法若已知运算符之间的优先关系，可按如下步骤构造优先函数：1、对每个运算符a（包括#在内）令f(a)=g(a)=12、如果a⋗b且f(a)<=g(b)令f(a)=g(b)+13、如果a⋖b且f(a)>=g(b)令g(b)=f(a)+14、如果a≐b而f(a)≠g(b)，令min{f(a),g(b)}=max{f(a),g(b)}5、重复2~4，直到过程收敛。如果重复过程中有一个值大于2n，则表明不存在算符优先函数。本例题中的算符优先函数+-*/（）#f335515

4、1g2244611当然，此时的算法和使用算符优先矩阵也是有一定差异的，本节课要求先从算符优先关系矩阵来获得算符优先函数，再用优先函数来实现表达式求值，并在实验报告中分析其与算符优先矩阵方法的优缺点。选做内容2（1）扩充运算符集合，如增加乘方、一元减和赋值等运算。（2）运算量可以是变量。（3）运算量可以是实数类型。（4）计算器的功能和仿真界面。