用兩種方法實現(xiàn)表達式自動計算

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一、設(shè)計思想計算算數(shù)表達式并求值，可以采取兩種算法：1.先將算術(shù)表達式轉(zhuǎn)化為后綴表達式，然后對后綴表達式進行計算。2.直接對算術(shù)表達式進行計算。下面依次對兩種方法進行分析：第一種算法有兩步1.先將算數(shù)表達式轉(zhuǎn)化為后綴表達式。在計算過程中，第一，要先建立一個存放操作符的棧和一個存放數(shù)字的數(shù)組。首先對用戶輸入的表達式進行掃面，如果是數(shù)字或者是小數(shù)點，直接存入數(shù)組。如果是操作符，就判斷是否為空或者是否為“（”或者是否它的優(yōu)先級大于操作符棧頂?shù)膬?yōu)先級，如果是，就入棧，索引后移；如果它的優(yōu)先級不大于棧頂操作符，棧頂?shù)牟僮鞣鰲＃M入數(shù)組，如此循環(huán)，直到棧頂?shù)膬?yōu)先級小于掃描到的操

2、作符的優(yōu)先級的時候，操作符入棧，索引后移。當遇到標識符0時，掃描結(jié)束。數(shù)組中存放的就是后綴表達式。2.利用后綴表達式進行計算。得到后綴表達式后，要計算就需要用到數(shù)值棧。首先對后綴表達式進行掃描，遇到數(shù)字字符，將數(shù)字字符轉(zhuǎn)化為浮點類型，放入數(shù)值棧中，遇到操作符，就從數(shù)值棧中取出兩個數(shù)，進行計算后將計算結(jié)果再放入數(shù)值棧中，掃描下一個，最后的計算結(jié)果就存到了數(shù)值棧中，直接取出數(shù)值棧棧頂元素，就是計算的最后結(jié)果。第二種算法首先要建立兩個棧，一個存放操作符的棧，一個是存放數(shù)值的棧。然后開始對用戶輸入的表達式進行掃描，如果是數(shù)值或是小數(shù)點，就將其轉(zhuǎn)化為浮點型數(shù)據(jù)，然后進入數(shù)值棧；如果是操作符，當前索引下的

3、操作符的優(yōu)先級如果不大于棧頂操作符的優(yōu)先級，就將棧頂操作符取出來，從數(shù)值棧中取出兩個數(shù)值，進行計算，結(jié)果存入數(shù)值棧。如此循環(huán)，直到棧頂操作符的優(yōu)先級小于當前索引的操作符的優(yōu)先級是，操作符入棧，然后對下一個字進行掃描。如果是左括號，則不進行優(yōu)先級的比較，直接入棧。如果是右括號，則從數(shù)值棧中取兩個操作數(shù)，符號棧中取出一個符號，然后進行計算后得數(shù)放入數(shù)棧中，不斷進行此類操作，直到從棧中取出的是左括號為止，左括號丟棄，掃描下一個。掃描結(jié)束后，數(shù)值棧中存放的數(shù)值就是計算產(chǎn)生的結(jié)果，最后把數(shù)值從數(shù)值棧中取出，就是所得的計算結(jié)果。二、算法流程圖第一種算法:先將表達式轉(zhuǎn)化為后綴表達式，然后計算表達式的值。 1

4、、中綴表達式轉(zhuǎn)化為后綴表達式說明：首先獲得算術(shù)運算符，對其進行掃面，如果是數(shù)字或者是小數(shù)點直接進入字符數(shù)組。如果是操作符，需要判斷它與操作符棧頂操作符的優(yōu)先級大小來決定是入棧還是棧頂出棧。如果是括號，左括號直接入棧，右括號從棧中找左括號，然后拋棄。掃描結(jié)束，字符數(shù)組中存放的就是后綴表達式，輸出即可。將中綴表達式轉(zhuǎn)化為后綴表達式流程圖如下：出棧入數(shù)組獲取表達式直接入棧不是左括號右括號看棧頂左括號哪種括號優(yōu)先級不大于棧頂元素棧頂元素出棧，放入字符數(shù)組與棧頂比較操作符直接放入字符數(shù)組小數(shù)點或者數(shù)字2、后綴表達式的計算說明：首先獲取后綴表達式，對表達式進行掃描，如果是數(shù)字轉(zhuǎn)換成相應(yīng)的浮點型數(shù)字，放入數(shù)

5、棧，如果是操作符，進行相應(yīng)的計算。后綴表達式的計算，實現(xiàn)的流程圖如下：入棧圖1 中綴表達式轉(zhuǎn)化為后綴表達式算法流程圖優(yōu)先級大于棧頂元素如果是括號掃描判斷得到后綴表達式掃描判斷轉(zhuǎn)換成浮點型，入數(shù)棧數(shù)字操作符數(shù)棧中取兩數(shù)字計算，結(jié)果入棧取出計算結(jié)果圖2 后綴表達式計算算法流程圖第二種算法：直接計算出結(jié)果直接計算出結(jié)果的算法流程圖如下：返回數(shù)棧棧頂元素獲取計算表達式掃描判斷轉(zhuǎn)換成浮點型，入數(shù)棧數(shù)字與棧頂比較操作符數(shù)棧取出兩個元素進行計算，結(jié)果入數(shù)棧直接入棧優(yōu)先級高優(yōu)先級低括號類型入棧棧中取出操作符括號左括號右括號是否“（”丟棄是不是數(shù)棧取出兩個元素進行計算，結(jié)果入數(shù)棧操作符棧是否空是操作符棧頂元素與

6、數(shù)棧取出兩個元素進行計算，結(jié)果入數(shù)棧不是圖3 直接進行表達式求值算法流程圖說明：首先得到要計算的表達式，并對其進行掃描，遇到的字符是數(shù)字，轉(zhuǎn)換成浮點型，入棧。如果是括號，視其左右，判斷是入棧或者是丟棄。如果是操作符，視其優(yōu)先級判斷是直接入棧還是進行計算。三、源代碼1、先轉(zhuǎn)換成后綴表達式，再進行表達式計算#include<stdio.h>#include<string.h>#include<math.h>#define MAXLENGTH 100 #define EMPTY -1 #define FULL 99typedef struct char op MA

7、XLENGTH;int p ;stack;typedef struct double numMAXLENGTH;int p;number;int Isempty (stack *ps) if (ps->p=EMPTY) return 1; else return 0;int Isfull ( stack *ps)if (ps->p = FULL)return 1;else return 0;int Push ( stack *ps,char ch)if (Isfull(ps)return 0;else ps->p +;ps->opps->p = ch ;retur

8、n 1;char Pop ( stack *ps )if (Isempty(ps)return 0;else return ps->opps->p-;char Top ( stack *ps)if (Isempty(ps)return 0;else return ps->opps->p;int Isemptyn (number *ps) if (ps->p=EMPTY) return 1; else return 0;int Isfulln ( number *ps)if (ps->p = FULL)return 1;else return 0;int Pu

9、shn ( number *ps,double dl)if (Isfulln(ps)return 0;else ps->p +;ps->numps->p = dl ;return 1;double Popn ( number *ps )if (Isemptyn(ps)return 0;else return ps->numps->p-;double Topn ( number *ps)if (Isemptyn(ps)return 0;else return ps->numps->p;int getoplevel(char c)if (c='+&

10、#39;|c='-')return 1;else if (c='*'|c='/'|c='%')return 2;else if (c='(')return 0;else return -1;void init(stack *mystack) mystack->p = EMPTY;void initnum(number *mynum)mynum->p = EMPTY;void calculate(char *mylist,stack *mystack)number mynum;int s=0 ;char

11、mynuMAXLENGTH;int smynu =0;double firstod ,secondod,result;double operand;initnum (&mynum);while(mylists!='0')if (mylists='+'|mylists='-'|mylists='*'|mylists='/'|mylists='%'|mylists=' ')switch(mylists)case '+':firstod = Popn(&my

12、num);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);secondod = Popn(&mynum);resul

13、t = secondod * firstod;Pushn(&mynum,result);break;case '/':firstod = Popn(&mynum);secondod = Popn(&mynum);if(firstod =0)printf("0 can not be dividorn ");return;result = secondod / firstod;Pushn(&mynum,result);break;case '%':firstod = Popn(&mynum);secondo

14、d = Popn(&mynum);result = (double)(int)secondod % (int)firstod);Pushn(&mynum,result);break;case ' ':break;s +;elsewhile (mylists<='9'&&mylists>='0'|mylists='.')mynusmynu = mylists;s +;smynu +;mynusmynu = '0'operand = atof(mynu);Pushn(&

15、;mynum,operand);smynu =0;result = Popn(&mynum);printf("結(jié)果是:");printf("%f n",result);void getexpression (char *myexp,stack mystack,char *mylist)int i =0;int s=0;int slist=0; while(myexps!='0') if(myexps<='9'&&myexps>='0'|myexps='.'

16、) while(myexps<='9'&&myexps>='0'|myexps='.') mylistslist = myexp s; s+; slist +; mylistslist=' ' slist+; else if (Isempty(&mystack)|myexps='(') Push(&mystack,myexps); s +; else if (myexps =')') while(Top(&mystack)!='('

17、) mylistslist = Pop(&mystack); slist +; mylistslist=' ' slist+; Pop(&mystack); s+; else if (getoplevel(myexps)>getoplevel(Top(&mystack) Push(&mystack,myexps); s+; else while(getoplevel(myexps)<=getoplevel(Top(&mystack) mylistslist = Pop(&mystack); slist +; mylis

18、tslist=' ' slist+; while(!Isempty(&mystack) mylistslist = Pop(&mystack); slist +; mylistslist=' ' slist+; mylistslist = '0' printf("后綴表達式為: n"); printf("%s",mylist); printf("n"); calculate(mylist,&mystack);void main()char myexp MAXLEN

19、GTH;stack mystack;char mylistMAXLENGTH ;printf("請輸入:n");gets(myexp);init(&mystack);getexpression(myexp,mystack,mylist); getch();2、 用直接計算表達式值#include<stdio.h>#include<math.h>#define MAXLENGTH 100 #define EMPTY -1 #define FULL 99 typedef struct char op MAXLENGTH; int p ;stack

20、;typedef struct double numMAXLENGTH;int p;number;int Isempty (stack *ps) if (ps->p=EMPTY) return 1; else return 0;int Isfull ( stack *ps)if (ps->p = FULL)return 1;else return 0;int Push ( stack *ps,char ch)if (Isfull(ps)return 0;else ps->p +;ps->opps->p = ch ;return 1;char Pop ( stack

21、 *ps )if (Isempty(ps)return 0;else return ps->opps->p-;char Top ( stack *ps)if (Isempty(ps)return 0;else return ps->opps->p;int Isemptyn (number *ps) if (ps->p=EMPTY) return 1; else return 0;int Isfulln ( number *ps)if (ps->p = FULL)return 1;else return 0;int Pushn ( number *ps,dou

22、ble dl)if (Isfulln(ps)return 0;else ps->p +;ps->numps->p = dl ;return 1;double Popn ( number *ps )if (Isemptyn(ps)return 0;else return ps->numps->p-;double Topn ( number *ps)if (Isemptyn(ps)return 0;else return ps->numps->p;int getoplevel(char c)if (c='+'|c='-')r

23、eturn 1;else if (c='*'|c='/'|c='%')return 2;else if (c='(')return 0;else return -1;void init(stack *mystack) mystack->p = EMPTY;void initnum(number *mynum)mynum->p = EMPTY;void calculate(char *myexp)stack mystack;number numstack;char mylistMAXLENGTH;int index =0

24、;int indexlist=0;double od1 ,od2;double result,operand ;init(&mystack);initnum(&numstack);while(myexpindex!='0')/if (myexpindex<='9'&&myexpindex>='0'|myexpindex='.')while(myexpindex<='9'&&myexpindex>='0'|myexpindex=&

25、#39;.')mylistindexlist = myexpindex;index +;indexlist +;mylistindexlist = '0'operand = atof(mylist);Pushn(&numstack,operand);indexlist = 0;else if(Isempty(&mystack)|myexpindex='('|getoplevel(myexpindex)>getoplevel(Top(&mystack)Push(&mystack,myexpindex);index +;

26、else if (myexpindex=')')while(Top(&mystack)!='(') od1 = Popn(&numstack);od2 = Popn(&numstack);switch(Top(&mystack)case '+': Pushn(&numstack,od2 + od1);break;case '-':Pushn(&numstack,od2 - od1);break;case '*':Pushn(&numstack,od2 * od

27、1);break;case '/':if(od1 =0)printf("0 can not be divisor n");return ;Pushn(&numstack,od2 / od1);break;case '%':Pushn(&numstack,(double)(int)od2 % (int)od1);break; Pop(&mystack); index +; Pop(&mystack); elsewhile(getoplevel(myexpindex)<=getoplevel(Top(&

28、;mystack)od1 = Popn(&numstack);od2 = Popn(&numstack);switch(Top(&mystack)case '+':Pushn(&numstack,od2 + od1);break;case '-':Pushn(&numstack,od2 - od1);break;case '*':Pushn(&numstack,od2 * od1);break;case '/':if(od1 =0) printf("0 不能做除數(shù)!請重新輸

29、入.n");return ;Pushn(&numstack,od2 / od1);break;case '%':Pushn(&numstack,(double)(int)od2 % (int)od1);break;Pop(&mystack);Push(&mystack,myexpindex);index +;while (!Isempty(&mystack)od1 = Popn(&numstack);od2 = Popn(&numstack);switch(Top(&mystack)case '+

30、':Pushn(&numstack,od2 + od1);break;case '-':Pushn(&numstack,od2 - od1);break;case '*':Pushn(&numstack,od2 * od1);break;case '/':if(od1 =0) printf("0 can not be divisor n");return ;Pushn(&numstack,od2 / od1);break;case '%':Pushn(&numst

31、ack,(double)(int)od2 % (int)od1);break;Pop(&mystack);result = Topn(&numstack);printf("The result is:n");printf("%f n",result);void main()char myexpMAXLENGTH;printf("Please input the expression:n");gets(myexp);calculate(myexp); getch();四、運行結(jié)果第一種算法程序運行結(jié)果圖：正確輸入表達式，

32、程序運行結(jié)果如圖：圖5 正確表達式運行結(jié)果圖第二種算法程序運行結(jié)果圖：正確輸入表達式，程序運行結(jié)果如圖：圖6 正確表達式運行結(jié)果圖五、遇到的問題及解決這部分我主要遇到了如下兩個問題，其內(nèi)容與解決方法如下所列：一要把后綴表達式放到了字符數(shù)組中，是如何將后綴表達式中的數(shù)字字符轉(zhuǎn)換成真正的數(shù)字？如果是單個的數(shù)字，可以進行強制轉(zhuǎn)換，但是數(shù)字不總都是單個的，我們要計算的數(shù)字往往是多位的如：12，或者帶有小數(shù)點如：1.2，那么怎么將其轉(zhuǎn)換成真正的浮點型的數(shù)字呢？解決方案：分析問題，我們知道重點是如何將多位的數(shù)字字符轉(zhuǎn)換成浮點型數(shù)字，同時也知道多位的數(shù)字字符是存儲地址是連續(xù)的，于是根據(jù)這個特點，我查閱了一下C語言庫函數(shù)，果然真的有符合條件的庫函數(shù)atof（）；首先atof（）函數(shù)在“math.h”頭文件下，引用“math.h”就可以使用atof（）函數(shù)直接將地址連續(xù)的多位數(shù)字字符轉(zhuǎn)換成相應(yīng)的浮點型數(shù)字。有了思路，我想到將字符數(shù)組中的數(shù)字按分隔符依次轉(zhuǎn)移到另一個字符數(shù)組中，并利用atof（）函數(shù)將其轉(zhuǎn)換成相應(yīng)的數(shù)字，但是