用两种方式实现表达式计.doc

《用两种方式实现表达式计.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、设计思想本项目用两种方式实现表达式自动计算：一是，用扫两遍表达式的方法；二是，用扫一遍表达式的方法。其算法如下：u算法一：扫两遍表达式求值的基本思路是：先将中缀表达式转化为后缀表达式，再通过计算后缀表达式求表达式的值。第一遍扫描中缀表达式，将其转换为后缀表达式，在这步中用到一个运算符栈和一个列表（用数组实现）。当扫到一个数时，因为运算数的位数不一定而且还有小数点，所以需要判断运算数的位数，将这个运算数按原来的顺序挂到列表中；当扫到一个运算符时，如果栈空：运算符直接入栈。栈不空时：遇到左括号，直接入栈；遇到右括号，则开始出栈挂到列表后，直到栈顶为左括号，左括号出栈；遇到

2、加、减、乘、除、求余运算符号时，当栈顶的运算符优先级低于扫到的运算符，运算符入栈，否则运算符出栈挂到列表后，直到满足入栈条件；当扫描完整个中缀表达式，将栈里面的运算符全都出栈挂列表后。另外，因为后缀表达式中两个运算数会连在一起，所以为了区分两个运算数，每当扫描到加、减、乘、除、求余运算符号和栈中运算符出栈挂表后，在列表中添加一个空格作为分隔符。这样列表中的表达式就是对应的后缀表达式。第二遍扫描后缀表达式，并计算，这步中用到一个栈来放扫描到的数。当扫到一个数时，因为运算数的位数不一定而且还有小数点，所以在扫到一个数时要判断这个数的位数，将这个完整的运算数字符串整个取出，把这

3、个字符串转化为数值型（如;利用atof（）函数将字符串转换为浮点型等），将其入栈；当扫到一个运算符时，则出栈两个数，先出栈的数作为第一个运算数后出栈的作为第二个运算数，按照所扫描到的运算符进行计算，并将计算结果放到栈中。当扫描完整个后缀表达式后，在栈中只有一个数，这个数就是我们所要求值的表达式的结果。u算法二：扫一遍表达式求值的基本思路是：用两个栈（一个字符栈、一个数字栈）边扫描边计算，最后在数字栈中所得的数就是计算结果。扫描要求值的表达式，当扫描到一个数时，因为运算数的位数不一定而且还有小数点，所以在扫到一个数时要判断这个数的位数，将这个完整的运算数字符串整个取出，把这

4、个字符串转化为数值型（如;利用atof（）函数将字符串转换为浮点型等），将其入数字栈。当扫描到一个运算符时，如果运算符栈空：运算符直接入运算符栈。运算符栈不空时：遇到左括号，直接入运算符栈；遇到右括号则从数字栈中出栈两个数，先出栈的数作为第一个运算数后出栈的作为第二个运算数，从运算符栈中出栈一个运算符，将两个数按照出栈运算符进行计算，并将计算结果放到数字栈中，直到运算符栈栈顶为左括号，左括号出栈；遇到加、减、乘、除、求余运算符号时，当运算符栈栈顶的运算符优先级低于扫到的运算符，运算符入运算符栈，否则从数字栈中出栈两个数，先出栈的数作为第一个运算数后出栈的作为第二个运算数，

5、从运算符栈中出栈一个运算符，将两个数按照出栈运算符进行计算，并将计算结果放到数字栈中，直到满足入栈条件。当扫描完整个表达式，如果运算符栈中不空，则从数字栈中出栈两个数，先出栈的数作为第一个运算数后出栈的作为第二个运算数，从运算符栈中出栈一个运算符，将两个数按照出栈运算符进行计算，并将计算结果放到数字栈中，直到运算符栈为空。这样，最后在数字栈中只有一个数了，这个数就是我们所要求值的表达式的结果。二、算法流程图开始初始化运算数栈和运算符栈输入一个表达式，存在数组exp1[]中扫描到数？扫描到（？扫描到）？exp1[index]==’’？扫描到+-*/%？是否否否否否否运算

6、符栈为空？运算符栈出栈一个运算符存到数组exp2[]输出数组exp2[]，即后缀表达式取出整个运算数，存入exp2[]数组中,入运算符栈栈顶为(？运算符栈出栈一个运算符存到数组exp2[]运算符栈中（出栈运算符优先级高于运算符栈顶？入运算符栈运算符栈出栈一个运算符存到数组exp2[]是否是否是是是是是是exp2[index]==’’？否运算符栈空？运算数栈出栈两个数运算符栈出栈一个运算符，计算结果入运算数栈是扫描到数？扫描到+-*/%？否是是输出运算数栈中的数即表达式的值结束是取出整个运算数，转换为浮点型，入运算数栈运算数栈出栈两个数与扫到运算符运算，计算结果入运算数

7、栈运算符优先级高于运算符栈顶？是否否入运算符栈否图1扫两遍算法流程图开始初始化运算数栈和运算符栈输入一个表达式，存在数组exp[]中扫描到数？扫描到（？扫描到）？exp[index]==’’？‘’扫描到+-*/%？是否否否否否否运算符栈为空？运算数栈出栈两个数运算符栈出栈一个运算符，计算结果入运算数栈输出运算数栈中的元素，即运算结果结束取出整个运算数，转换为浮点型，入运算数栈入运算符栈栈顶为（？运算数栈出栈两个数运算符栈出栈一个运算符，计算结果入运算数栈运算符栈中（出栈运算符优先级高于运算符栈顶？入运算符栈运算数栈出栈