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

用两种方法实现表达式自动计算1一、设计思想计算算数表达式并求值，可以采取两种算法：1.先将算术表达式转化为后缀表达式，然后对后缀表达式进行计算。2.直接对算术表达式进行计算。下面依次对两种方法进行分析：第一种算法有两步1.先将算数表达式转化为后缀表达式。在计算过程中，第一，要先建立一个存放操作符的栈和一个存放数字的数组。首先对用户输入的表达式进行扫面，如果是数字或者是小数点，直接存入数组。如果是操作符，就判断是否为空或者是否为“（”或者是否它的优先级大于操作符栈顶的优先级，如果是，就入栈，索引后移；如果它的优先级不大于栈顶操作符，栈顶的操作符出栈，进入数组，如此循环，直到栈顶的优先级小于扫描到的操作符的优先级的时候，操作符入栈，索引后移。当遇到标识符\0时，扫描结束。数组中存放的就是后缀表达式。2.利用后缀表达式进行计算。得到后缀表达式后，要计算就需要用到数值栈。首先对后缀表达式进行扫描，遇到数字字符，将数字字符转化为浮点类型，放入数值栈中，遇到操作符，就从数值栈中取出两个数，进行计算后将计算结果再放入数值栈中，扫描下一个，最后的计算结果就存到了数值栈中，直接取出数值栈栈顶元素，就是计算的最后结果。第二种算法首先要建立两个栈，一个存放操作符的栈，一个是存放数值的栈。然后开始对用户输入的表达式进行扫描，如果是数值或是小数点，就将其转化为浮点型数据，然后进入数值栈；如果是操作符，当前索引下的操作符的优先级如果不大于栈顶操作符的优先级，就将栈顶操作符取出来，从数值栈中取出两个数值，进行计算，结果存入数值栈。如此循环，直到栈顶操作符的优先级小于当前索引的操作符的优先级是，操作符入栈，然后对下一个字进行扫描。如果是左括号，则不进行优先级的比较，直接入栈。如果是右括号，则从数值栈中取两个操作数，符号栈中取出一个符号，然后进行计算后得数放入数栈中，不断进行此类操作，直到从栈中取出的是左括号为止，左括号丢弃，扫描下一个。扫描结束后，数值栈中存放的数值就是计算产生的结果，最后把数值从数值栈中取出，就是所得的计算结果。二、算法流程图第一种算法:先将表达式转化为后缀表达式，然后计算表达式的值。1、中缀表达式转化为后缀表达式说明：首先获得算术运算符，对其进行扫面，如果是数字或者是小数点直接进入字符数组。如果是操作符，需要判断它与操作符栈顶操作符的优先级大小来决定是入栈还是栈顶出栈。如果是括号，左括号直接入栈，右括号从栈中找左括号，然后抛弃。扫描结束，字符数组中存放的就是后缀表达式，输出即可。将中缀表达式转化为后缀表达式流程图如下：用两种方法实现表达式自动计算2优先级大于栈顶元素入栈扫描判断如果是括号获取表达式小数点或者数字直接放入字符数组操作符与栈顶比较栈顶元素出栈，放入字符数组优先级不大于栈顶元素哪种括号直接入栈左括号看栈顶右括号不是左括号出栈入数组图1中缀表达式转化为后缀表达式算法流程图2、后缀表达式的计算说明：首先获取后缀表达式，对表达式进行扫描，如果是数字转换成相应的浮点型数字，放入数栈，如果是操作符，进行相应的计算。后缀表达式的计算，实现的流程图如下：用两种方法实现表达式自动计算3图2后缀表达式计算算法流程图第二种算法：直接计算出结果直接计算出结果的算法流程图如下：图3直接进行表达式求值算法流程图返回数栈栈顶元素获取计算表达式扫描判断转换成浮点型，入数栈数字与栈顶比较操作符数栈取出两个元素进行计算，结果入数栈直接入栈优先级高优先级低括号类型入栈栈中取出操作符括号左括号右括号是否“（”丢弃是不是数栈取出两个元素进行计算，结果入数栈操作符栈是否空是操作符栈顶元素与数栈取出两个元素进行计算，结果入数栈不是得到后缀表达式扫描判断转换成浮点型，入数栈数字操作符数栈中取两数字计算，结果入栈取出计算结果用两种方法实现表达式自动计算4说明：首先得到要计算的表达式，并对其进行扫描，遇到的字符是数字，转换成浮点型，入栈。如果是括号，视其左右，判断是入栈或者是丢弃。如果是操作符，视其优先级判断是直接入栈还是进行计算。三、源代码1、先转换成后缀表达式，再进行表达式计算#includestdio.h#includestring.h#includemath.h#defineMAXLENGTH100#defineEMPTY-1#defineFULL99typedefstruct{charop[MAXLENGTH];intp;}stack;typedefstruct{doublenum[MAXLENGTH];intp;}number;intIsempty(stack*ps){if(ps-p==EMPTY)return1;elsereturn0;}intIsfull(stack*ps){if(ps-p==FULL)return1;elsereturn0;}intPush(stack*ps,charch){用两种方法实现表达式自动计算5if(Isfull(ps))return0;else{ps-p++;ps-op[ps-p]=ch;return1;}}charPop(stack*ps){if(Isempty(ps))return0;else{returnps-op[ps-p--];}}charTop(stack*ps){if(Isempty(ps))return0;elsereturnps-op[ps-p];}intIsemptyn(number*ps){if(ps-p==EMPTY)return1;elsereturn0;}intIsfulln(number*ps){if(ps-p==FULL)return1;elsereturn0;}用两种方法实现表达式自动计算6intPushn(number*ps,doubledl){if(Isfulln(ps))return0;else{ps-p++;ps-num[ps-p]=dl;return1;}}doublePopn(number*ps){if(Isemptyn(ps))return0;else{returnps-num[ps-p--];}}doubleTopn(number*ps){if(Isemptyn(ps))return0;elsereturnps-num[ps-p];}intgetoplevel(charc){if(c=='+'||c=='-'){return1;}elseif(c=='*'||c=='/'||c=='%'){return2;}elseif(c=='('){return0;用两种方法实现表达式自动计算7}elsereturn-1;}voidinit(stack*mystack){mystack-p=EMPTY;}voidinitnum(number*mynum){mynum-p=EMPTY;}voidcalculate(char*mylist,stack*mystack){numbermynum;ints=0;charmynu[MAXLENGTH];intsmynu=0;doublefirstod,secondod,result;doubleoperand;initnum(&mynum);while(mylist[s]!='\0'){if(mylist[s]=='+'||mylist[s]=='-'||mylist[s]=='*'||mylist[s]=='/'||mylist[s]=='%'||mylist[s]==''){switch(mylist[s]){case'+':firstod=Popn(&mynum);secondod=Popn(&mynum);result=secondod+firstod;Pushn(&mynum,result);break;case'-':firstod=Popn(&mynum);secondod=Popn(&mynum);result=secondod-firstod;Pushn(&mynum,result);break;case'*':firstod=Popn(&mynum);用两种方法实现表达式自动计算8secondod=Popn(&mynum);result=secondod*firstod;Pushn(&mynum,result);break;case'/':firstod=Popn(&mynum);secondod=Popn(&mynum);if(firstod==0){printf(0cannotbedividor\n);return;}result=secondod/firstod;Pushn(&mynum,result);break;case'%':firstod=Popn(&mynum);secondod=Popn(&mynum);result=(double)((int)secondod%(int)firstod);Pushn(&mynum,result);break;case'':break;}s++;}else{while(mylist[s]='9'&&mylist[s]='0'||mylist[s]=='.'){mynu[smynu]=mylist[s];s++;smynu++;}mynu[smynu]='\0';operand=atof(mynu);Pushn(&mynum,operand);smynu=0;}}result=Popn(&mynum);printf(结果是:);printf(%f\n,result);}用两种方法实现表达式自动计算9voidgetexpression(char*myexp,stackmystack,char*mylist){inti=0;ints=0;intslist=0;while(myexp[s]!='\0'){if(myexp[s]='9'&&myexp[s]='0'||myexp[s]=='.'){while(myexp[s]='9'&&myexp[s]='0'||myexp[s]=='.'){mylist[slist]=myexp[s];s++;slist++;}mylist[slist]='';slist++;}else{if(Isempty(&mystack)||myexp[s]=='('){Push(&mystack,myexp[s]);s++;}elseif(myexp[s]==')'){while(Top(&mystack)!='('){mylist[slist]=Pop(&mystack);slist++;mylist[slist]='';slist++;}Pop(&mystack);s++;}elseif(getoplevel(myexp[s])getoplevel(Top(&mystack))){Push(&mystack,myexp[s]);s++;用两种方法实现表达式自动计算10}else{while(getoplevel(myexp[s])=getoplevel(Top(&mystack))){mylist[slist]=Pop(&mystack);slist++;mylist[slist]='';slist++;}}}}while(!Isempty(&mystack)){mylist[slist]=Pop(&mystack);slist++;mylist[slist]='';slist++;}mylist[slist]='\0';printf(后缀表达式为:\n);printf(%s,mylist);printf(\n);calculate(mylist,&mystack);}voidmain(){charmyexp[MAXLENGTH];stackmystack;charmylist[MAXLENGTH];printf(请输入:\n);gets(myexp);init(&mystack);getexpression(myexp,mystack,mylist);getch();}用两种方