用两种方法实现表达式自动计算.doc

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

1、一、设计思想计算算数表达式并求值，可以采取两种算法：1.先将算术表达式转化为后缀表达式，然后对后缀表达式进行计算。2.直接对算术表达式进行计算。下面依次对两种方法进行分析：第一种算法有两步1.先将算数表达式转化为后缀表达式。在计算过程中，第一，要先建立一个存放操作符的栈和一个存放数字的数组。首先对用户输入的表达式进行扫面，如果是数字或者是小数点，直接存入数组。如果是操作符，就判断是否为空或者是否为“（”或者是否它的优先级大于操作符栈顶的优先级，如果是，就入栈，索引后移；如果它的优先级不大于栈顶操作符，栈顶的操作符

2、出栈，进入数组，如此循环，直到栈顶的优先级小于扫描到的操作符的优先级的时候，操作符入栈，索引后移。当遇到标识符时，扫描结束。数组中存放的就是后缀表达式。2.利用后缀表达式进行计算。得到后缀表达式后，要计算就需要用到数值栈。首先对后缀表达式进行扫描，遇到数字字符，将数字字符转化为浮点类型，放入数值栈中，遇到操作符，就从数值栈中取出两个数，进行计算后将计算结果再放入数值栈中，扫描下一个，最后的计算结果就存到了数值栈中，直接取出数值栈栈顶元素，就是计算的最后结果。第二种算法首先要建立两个栈，一个存放操作符的栈，一个

3、是存放数值的栈。然后开始对用户输入的表达式进行扫描，如果是数值或是小数点，就将其转化为浮点型数据，然后进入数值栈；如果是操作符，当前索引下的操作符的优先级如果不大于栈顶操作符的优先级，就将栈顶操作符取出来，从数值栈中取出两个数值，进行计算，结果存入数值栈。如此循环，直到栈顶操作符的优先级小于当前索引的操作符的优先级是，操作符入栈，然后对下一个字进行扫描。如果是左括号，则不进行优先级的比较，直接入栈。如果是右括号，则从数值栈中取两个操作数，符号栈中取出一个符号，然后进行计算后得数放入数栈中，不断进行此类操作，直到从

4、栈中取出的是左括号为止，左括号丢弃，扫描下一个。扫描结束后，数值栈中存放的数值就是计算产生的结果，最后把数值从数值栈中取出，就是所得的计算结果。二、算法流程图第一种算法:先将表达式转化为后缀表达式，然后计算表达式的值。1、中缀表达式转化为后缀表达式说明：首先获得算术运算符，对其进行扫面，如果是数字或者是小数点直接进入字符数组。如果是操作符，需要判断它与操作符栈顶操作符的优先级大小来决定是入栈还是栈顶出栈。如果是括号，左括号直接入栈，右括号从栈中找左括号，然后抛弃。扫描结束，字符数组中存放的就是后缀表达式，输出即可

5、。将中缀表达式转化为后缀表达式流程图如下：出栈入数组获取表达式直接入栈不是左括号右括号看栈顶左括号哪种括号优先级不大于栈顶元素栈顶元素出栈，放入字符数组与栈顶比较操作符直接放入字符数组小数点或者数字2、后缀表达式的计算说明：首先获取后缀表达式，对表达式进行扫描，如果是数字转换成相应的浮点型数字，放入数栈，如果是操作符，进行相应的计算。后缀表达式的计算，实现的流程图如下：入栈图1中缀表达式转化为后缀表达式算法流程图优先级大于栈顶元素如果是括号扫描判断得到后缀表达式扫描判断转换成浮点型，入数栈数字操作符数栈中取两数字

6、计算，结果入栈取出计算结果图2后缀表达式计算算法流程图第二种算法：直接计算出结果直接计算出结果的算法流程图如下：返回数栈栈顶元素获取计算表达式扫描判断转换成浮点型，入数栈数字与栈顶比较操作符数栈取出两个元素进行计算，结果入数栈直接入栈优先级高优先级低括号类型入栈栈中取出操作符括号左括号右括号是否“（”丢弃是不是数栈取出两个元素进行计算，结果入数栈操作符栈是否空是操作符栈顶元素与数栈取出两个元素进行计算，结果入数栈不是图3直接进行表达式求值算法流程图说明：首先得到要计算的表达式，并对其进行扫描，遇到的字符是数字，转

7、换成浮点型，入栈。如果是括号，视其左右，判断是入栈或者是丢弃。如果是操作符，视其优先级判断是直接入栈还是进行计算。三、源代码1、先转换成后缀表达式，再进行表达式计算#include#include#include#defineMAXLENGTH100#defineEMPTY-1#defineFULL99typedefstruct{charop[MAXLENGTH];intp;}stack;typedefstruct{doublenum[MAXLENGTH];i

8、ntp;}number;intIsempty(stack*ps){if(ps->p==EMPTY)return1;elsereturn0;}intIsfull(stack*ps){if(ps->p==FULL)return1;elsereturn0;}intPush(stack*ps,charch){if(Isfull(ps))return0;else{ps->p++;p