1、用兩種方式實現表達式自動計算一、設計思想計算算數表達式并求值，采取的共有兩種方法：1. 先將算數表達式轉化為后綴表達式，然后對后綴表達式進行計算。2. 對算數表達式進行直接的計算。第一種算法這種解決方案又分為兩步：1.將表達式先轉化為后綴表達式的字符串數組2.利用后綴表達式進行計算在轉化過程中，第一，建立一個存符號的棧，和一個字符串數組，用來存放轉化以后的表達式然后，對于得到的用戶輸入的字符串進行逐個的掃描，如果是數組或者小數點，則直接存放到數組中，并且在后面加入一個分隔符，如果是操作符，則和棧中的已存的進行比較，如果比棧中的操作符的優先級高，則直接入棧，如果優先級低或相等，則棧中元素出棧，存

2、到字符串中，然后再次檢查棧頂，直到棧中元素的優先級低于掃描操作符，則此操作符入棧，然后掃描下一個字符，直到遇到字符串的結束符號0，掃描結束。數組中存的就是后綴表達式。得到后綴表達式后，進行計算，要用到數值棧。首先要將字符表示的數字轉化為浮點小數，然后進行掃描，遇到數值，放入棧中，遇到操作符，就從棧中取出兩個數，進行計算后再放入棧中，掃描下一個，最后的計算結果就存到了棧中，直接取出棧內元素，就是計算的最后結果。第二種算發首先要建立兩個棧，一個用來存放操作符，一個用來存放數值。開始對用戶輸入的字符串進行掃描，如果是數字字符或者小數點，則將字符轉化為浮點數存到數棧里，如果是操作符，則觀察符號棧，如果

3、棧頂元素的優先級低于觀察的操作符，則操作符入棧，如果棧頂元素的優先級高于或者等于觀察的操作符，則從數值棧中取出兩個浮點數，從符號棧中取出棧頂的操作符，然后進行相應的數值計算，所得的結果再存到數值棧中，重復這樣的操作，直到符號棧中棧頂元素的優先級低于觀察的操作符，則此操作符入棧，然后對下一個字符進行掃描。如果是左括號，則不進行優先級的比較，直接入棧，入棧后優先級為-1。如果是右括號，則從數值棧中取兩個操作數，符號棧中取出一個符號，然后進行計算后得數放入數棧中，不斷進行此類操作，直到從棧中取出的是左括號為止，左括號去掉，掃描下一個。掃描結束后，計算也結束了，計算的結果就存放在數值棧中，最后把數值棧

4、中的數取出，就是所得的計算結果。容錯的算法簡要：括號匹配：當掃描到左括號是，左括號直接入棧，掃描到右括號時，則左括號出棧，如果棧為空，則右括號多，如果最后棧中還有括號，則左括號多。給出錯誤提示。除數不為0：當掃描到/時，就判斷其后面的數字是否為0，如果為0報錯。取余運算：取余運算時，操作數判斷是否為整數，不為整數報錯。二、算法流程圖第一種算法:先將表達式轉化為后綴表達式，然后計算其主函數流程圖為： 得到用戶輸入的中綴表達式調用容錯函數存在錯誤 報錯并結束無錯調用函數得到后綴表達式后綴表達式的計算返回計算結果調用直接計算的函數返回直接計算的結果圖1 主函數算法流程圖其中將中綴表達式轉化為后綴表達

5、式的主要流程為：取得字符并判斷如果是數字或小數點直接放入字符數組中在其后加入分隔符如果是操作符與棧頂比較判斷哪類括號直接入棧右括號取出不為(從棧中取出操作符放入數組直接入棧優先級高于棧頂如果是括號出棧存入數組中左括號優先級不高于棧頂圖2 中綴轉化為后綴算法流程圖后綴表達式的計算，實現的流程圖為：從數棧取2個數做相應計算結果存入數棧判斷符號類型得到后綴表達式數字字符操作符轉化為浮點數入棧從數棧中取出計算結果作為返回值圖3 后綴表達式計算算法流程圖下面介紹直接計算出結果的算法的實現：棧非空棧空低于棧頂高于棧頂NOYES左括號得到中綴表達式從字符串中取出一個字符判斷字符類型數字字符操作符轉化為浮點數

6、入棧括號括號類型直接入棧右括號從棧中取出操作符是否為（丟棄（放入數組與棧頂比較直接入棧取出棧頂兩個數作相應計算結果存入數棧符號棧是否為空將數值棧頂返回取棧頂符號與2個數計算，結果存入數值棧圖4 直接計算中綴表達式算法流程圖三、源代碼下面給出的是用先轉后綴再計算和直接計算的算法實現的程序的源代碼：#include /*導入需要用到的各種包*/#include#includetypedef struct /*定義結構體用來存儲操作符*/char op; /*存儲字符*/int level; /*存儲優先級*/OpNode;typedef struct OpNode op100; int top;

7、int size; /*表示棧內元素的個數*/ stack; /*定義符號棧*/void init(stack *st) /*初始化棧*/ st-size=0; st-top=0;OpNode pop(stack *a) / *出棧*/ if (a-size=0) /*如果棧為空結束操作*/ exit(-1); a-size-; return a-op-(a-top); /*取出棧頂元素*/void push(stack *a,OpNode op) /*入棧函數*/ a-size+; a-op(a-top)+=op;OpNode top(stack *a) /*觀察棧頂函數*/ if (a-s

8、ize=0) /*如果棧為空結束操作*/ printf(stack is emptyn); exit(-1); return a-op(a-top)-1; /*只得到棧頂的值而不出棧*/typedef struct /*定義數值棧*/ double num100; int top; /*棧頂指針*/ int size; numstack;void init2(numstack *st) /*初始化數值棧*/ st-size=0; st-top=0;double pop2(numstack *a) /*數值棧出棧*/ if (a-size=0) /*出棧前的判空*/ exit(-1); a-si

9、ze-; return a-num-(a-top); /*得到棧頂的值*/void push2(numstack *a,double num) /*入棧*/ a-size+; a-num(a-top)+=num;void main() /*主函數*/ void change (char str,char exp); /*聲明要用到的各個函數*/ double CalResult(char exp); /*聲明后綴表達式的計算函數*/ double Directcalresult(char str); int check(char str,char chestr100); char str100

10、,exp100,chestr100; /*str存儲原算術表達式，exp存儲對應的 printf(算術表達式為:n); 后綴表達式,chestr存儲容錯字符*/ gets(str); if(check(str,chestr) /*調用容錯函數*/ printf(表達式錯在：n); printf(%sn,str); printf(chestr); /*根據輸入情況指出錯誤的地方*/ exit(-1); change(str,exp); /*調用函數將中綴轉化為后綴*/ printf(后綴表達式為:%sn,exp); printf(運算結果為： %fn,CalResult(exp); /*調用函數

11、計算后綴表達式*/ printf(直接運算的結果為: %fn,Directcalresult(str); /*調用直接計算函數*/void change (char str,char ch) /*將前綴表達式轉化為后綴表達式*/int i=0; /*str的索引*/int k=0;char c; /*字符串中取出的放在C中*/stack st; /*定義符號棧*/OpNode op;OpNode ops;init(&st); /*初始化符號棧*/c=stri+; while (c!=0) /*對字符串進行掃描*/if ( (c=0&c=0&c0) /*再次檢查棧是否為空，*/op=top(&s

12、t); else break; /*為空就結束*/pop(&st); /*去掉左括號*/if (c=+|c=-) /*如果是+-號*/ op.op=c;op.level=1; /*優先級為1*/ if (st.size=0)push(&st,op); /*如果此時棧為空直接入棧*/else ops=top(&st); /*觀察棧頂*/ while (ops.level=op.level) /*如果棧頂優先級高*/ ops=pop(&st); chk+=ops.op; /*將棧頂元素取出存入數組中*/ if (st.size0)ops=top(&st); /*進行判空操作，棧為空結束*/ els

13、e break; push(&st,op); /*此時棧頂優先級低，入棧*/if(c=*|c=/|c=%) /*如果是*/進行*/op.op=c; op.level=2; /*優先級為1*/ if (st.size=0)push(&st,op); /*如果此時棧為空直接入棧*/else ops=top(&st); /*觀察棧頂*/ while (ops.level=op.level) /*如果棧頂優先級高*/ ops=pop(&st); /*將棧頂元素取出存入數組中*/ chk+=ops.op; if (st.size0)ops=top(&st); /*進行判空操作，棧為空結束*/ else

14、break;push(&st,op); /*此時棧頂優先級低，入棧*/c=stri+; /*索引自加檢索下一個字符*/ while(st.size!=0) /*最后判斷棧如果不為空*/ops=pop(&st); /*取出棧內元素存入數組中*/chk+=ops.op; chk=0; /*將0作為結尾存入數組*/double CalResult(char exp) /*后綴表達式的計算*/ char c; numstack numst; /*建立數值棧*/ double d1,d2,dr; int k=0; /*后綴表達式的索引*/ int i=0; /*將字符轉化為浮點數的索引*/ char *

15、s; char trans100; /*存字符表示的一段數字*/ init2 (&numst); /*實現數值棧*/ c=expk+; while (c!=0) /*開始掃描后綴表達式*/ if(c=+|c=-|c=*|c=/|c=%) /*如果是操作符*/ switch(c) case + : /*如果是加法操作*/ d2=pop2(&numst); d1=pop2(&numst); dr=d1+d2; /*相加后入棧*/ push2(&numst,dr); break; case - : /*如果是減法操作*/ d2=pop2(&numst); d1=pop2(&numst); dr=d1

16、-d2; /*相減后入棧*/ push2(&numst,dr); break; case * : /*如果是乘法操作*/ d2=pop2(&numst); d1=pop2(&numst); dr=d1*d2; /*相乘后入棧*/ push2(&numst,dr); break; case / : /*如果是除法操作*/ d2=pop2(&numst); d1=pop2(&numst); dr=d1/d2; /*相除后入棧*/ push2(&numst,dr); break; case % : /*如果是取余操作*/ d2=pop2(&numst); d1=pop2(&numst); dr=(d

17、ouble)(int)d1%(int)d2); /*類型轉化并取余后入棧*/ push2(&numst,dr); break; if (c=0&c=0&c=9|c=.)transi+=c; /*將字符存入數組進行下一個的掃描*/c=expk+; transi+=0; /*將表示數字的字符串結束*/ i=0;s=trans; /*將指針指向該數組*/d1=atof(s); /*利用函數將字符串轉化為浮點數*/push2(&numst,d1); c=expk+; return pop2(&numst); /*最后結果將在數值棧中，取出作為返回值*/double Directcalresult(ch

18、ar str) /*表達式的直接計算出結果*/ stack ms; /*建立符號棧*/ numstack mns; /*建立數值棧*/ double calculate(double od1,double od2,OpNode op); int index=0; /*str的索引*/ int len=strlen(str); char c; char trans100; /*存放數值的一段字符*/ int i=0; /*trans的索引*/ char * s; double d; OpNode tempn; /*存放當前掃描的操作符*/ OpNode templn; double oda,od

19、b,odr; double result; /*作為返回值返回結果*/ init (&ms); /*實現兩個棧*/ init2(&mns); while(index=0&c=0&c=tempn.level) /*棧頂優先級高*/ templn=pop(&ms); /*取出操作數和操作符計算*/ odb=pop2(&mns); oda=pop2(&mns); odr=calculate(oda,odb,templn); push2(&mns,odr); /*結算結果入棧*/ if(ms.size0) templn=top(&ms); /*如果棧空結束*/ else break; push(&ms

20、,tempn); /*操作符入棧*/ if(c=*|c=/|c=%) /*如果是*/%操作*/ tempn.level=2; /*定義優先級為2*/ tempn.op=c; if(ms.size=0) push(&ms,tempn); /*棧空直接入棧*/ else templn=top(&ms); while (templn.level=tempn.level) /*棧頂優先級高*/ templn=pop(&ms); /*取出操作數和操作符計算*/ odb=pop2(&mns); oda=pop2(&mns); odr=calculate(oda,odb,templn); push2(&mn

21、s,odr); /*結算結果入棧*/ if(ms.size0) templn=top(&ms); else break; /*如果棧空結束*/ templn=top(&ms); push(&ms,tempn); /*操作符入棧*/ if(c=() /*如果是左括號*/ tempn.level=-1; tempn.op=c; /*直接入棧優先級定位-1*/ push(&ms,tempn); if(c=) /*如果是右括號*/ while(tempn.op!=() /*遇到左括號結束*/ templn=pop(&ms); odb=pop2(&mns); /*從數棧中取兩個數，從符號棧里取操作符*/

22、 oda=pop2(&mns); odr=calculate(oda,odb,templn); /*計算出結果入棧*/ push2(&mns,odr); if (ms.size0) tempn=top(&ms); else break; /*如果棧空結束*/ pop(&ms); /*取出左括號*/ tempn=top(&ms); while(1) templn=pop(&ms); odb=pop2(&mns); /*從數棧中取兩個數，從符號棧里取操作符*/ oda=pop2(&mns); odr=calculate(oda,odb,templn); /*計算出結果入棧*/ push2(&mns

23、,odr); if (ms.size0)tempn=top(&ms); /*如果棧空結束*/ else break; result =pop2(&mns); /*最后的結果在數值棧中返回*/ return result;double calculate(double od1,double od2,OpNode op) /*已知操作符和操作數的計算*/ switch(op.op) case + : return od1+od2; case - : return od1-od2; /*判斷操作符是哪個執行相應計算*/ case * : return od1*od2; case / : return

24、 od1/od2; case % : return (double)(int)od1%(int)od2);return 0; /*如果上面的都沒有執行返回0*/int check(char str,char chestr100) /*容錯函數*/ char c; char cdivide; int i=0; /*str的索引*/ stack che; /*括號匹配用到的棧*/ OpNode temp; int k=0; /*chestr的索引*/ int isinteger(char integer100); /*%計算是判斷是否是整數*/ char s110; /*%操作時存儲%左右的數字*

25、/ char s210; int indexs1=0; /*s1s2的索引*/ int indexs2=0; init (&che); int flag=0; /*0沒有出錯1有錯*/ int tag=0; c=stri; /*開始掃描*/ int j; /*數組chestr索引*/ for(j=0;j0) pop(&che); /*棧不為空就取出一個左括號*/ else flag=1; printf(缺少左括號n); /*否則提示有錯*/ chestri=; /*右括號下加*/ if(c=/) /*判斷除數是否為0*/ j=0; cdivide=stri+1+j; /*取出除號后的數*/ w

26、hile(cdivide=0&cdivide=0&stri-indexs1-1=0&stri+indexs2+10) /*如果最后棧不為空*/ printf(缺少右括號n); /*棧中還有沒配對的左括號報錯*/ return flag; /*返回是否有錯*/int isinteger(char integer100) /*判斷數組內是否是整數*/int i=0; /*傳過來的數組的索引*/char c;c=integeri+;while(c!=0) /*直到字符串最后掃描結束*/ if(c=.) /*只要有一個字符為小數點就不是整數*/return 1;elsec=integeri+; /*掃

27、描下一個*/return 0;4、 運行結果在輸入表達式沒有錯誤的情況下，可以得到兩種算法的運算結果為：圖5 表達式正確時兩種算法運行結果圖如果表達式的輸入有錯誤，運行結果分別如下：1.除數為0圖6 除數為0提示錯誤圖2. 取余運算操作數不為整數：圖7取余操作數不為整提示錯誤圖3.括號匹配的問題：圖8 缺少左括號提示錯誤圖圖9缺少右括號提示錯誤圖五、遇到的問題及解決在編程的時候總是會有很多的意想不到的為題出現。這部分我主要遇到了如下兩個問題，其內容與解決方法如下所列：l 將字符表示的數字轉化為浮點數這個操作的主要目的就是數字是用一串字符表示的，在計算的過程中就要把字符串轉化成對應的浮點數，要解決這個問題，首