C語言后綴表達(dá)式計(jì)算

1、.一、設(shè)計(jì)思想計(jì)算算數(shù)表達(dá)式并求值，實(shí)行的共有兩種方法：先將算數(shù)表達(dá)式轉(zhuǎn)化為后綴表達(dá)式，然后對后綴表達(dá)式進(jìn)行計(jì)算。對算數(shù)表達(dá)式進(jìn)行直接的計(jì)算。第一種算法這種解決方案又分為兩步：將表達(dá)式先轉(zhuǎn)化為后綴表達(dá)式的字符串?dāng)?shù)組利用后綴表達(dá)式進(jìn)行計(jì)算表達(dá)式 存放到數(shù)組中，并且在后面加入一個(gè)分隔符，假如是操作符，則和棧中的已存的進(jìn)行比較， 0 數(shù)，然后進(jìn)行掃描，遇到數(shù)值，放入棧中，遇到操作符，就從棧中取出兩個(gè)數(shù)，進(jìn)行計(jì)算后再放入棧中，掃描下一個(gè)，最終的計(jì)算結(jié)果就存到了棧中，直接取出棧內(nèi)元素，就是計(jì)算的最終結(jié)果。其次種算發(fā) 行掃描，假如是數(shù)字字符或者小數(shù)點(diǎn)，則將字符轉(zhuǎn)化為浮點(diǎn)數(shù)存到數(shù)棧里，假如是操作符， 號(hào)棧中

2、棧頂元素的優(yōu)先級(jí)低于觀看的操作符1。假如是右括號(hào)，則 進(jìn)行此類操作，直到從棧中取出的是左括號(hào)為止，左括號(hào)去掉，掃描下一個(gè)。掃描結(jié)束后， 結(jié)果。容錯(cuò)的算法簡要：括號(hào)匹配：當(dāng)掃描到左括號(hào)是，左括號(hào)直接入棧，掃描到右括號(hào)時(shí)，則左括號(hào)出棧，假如棧為空，則右括號(hào)多，假如最終棧中還有括號(hào)，則左括號(hào)多。給出錯(cuò)誤提示。0：當(dāng)掃描到/0，0取余運(yùn)算：取余運(yùn)算時(shí)，操作數(shù)推斷是否為整數(shù)，不為整數(shù)報(bào)錯(cuò)。二、算法流程圖第一種算法:先將表達(dá)式轉(zhuǎn)化為后綴表達(dá)式，然后計(jì)算其主函數(shù)流程圖為：.假如是數(shù)字假如是操作符取得字符假如是數(shù)字假如是操作符取得字符或小數(shù)點(diǎn)并推斷優(yōu)先級(jí)高于棧頂直接放入字符數(shù)組中與棧頂比較直接入棧在其后加入分

3、隔符假如是括號(hào)左括號(hào)推斷哪類括號(hào)優(yōu)先級(jí)不高于棧頂出棧存入數(shù)組中直接入棧右括號(hào)從棧中取出操作符放入數(shù)組取出不為(存在錯(cuò)誤存在錯(cuò)誤報(bào)錯(cuò)并結(jié)束得到用戶輸入的中綴表達(dá)式調(diào)用容錯(cuò)函數(shù)得到用戶輸入的中綴表達(dá)式調(diào)用容錯(cuò)函數(shù)返回計(jì)算結(jié)果無錯(cuò)返回直接計(jì)算的結(jié)果調(diào)用函數(shù)得到后綴表達(dá)式后綴表達(dá)式的計(jì)算調(diào)用直接計(jì)算的函數(shù)其中將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式的主要流程為：2 中綴轉(zhuǎn)化為后綴算法流程圖.得到后綴表達(dá)式數(shù)字字符得到后綴表達(dá)式數(shù)字字符操作符推斷符號(hào)類型轉(zhuǎn)化為浮點(diǎn)數(shù)入棧2 個(gè)數(shù)做相應(yīng)計(jì)算結(jié)果存入數(shù)棧從數(shù)棧中取出計(jì)算結(jié)果作為返回值3 后綴表達(dá)式計(jì)算算法流程圖下面介紹直接計(jì)算出結(jié)果的算法的實(shí)現(xiàn)：得到中綴表達(dá)式得到中綴表

4、達(dá)式從字符串中取出一個(gè)字符數(shù)字字符操作符推斷字符類型轉(zhuǎn)化為浮點(diǎn)數(shù)入棧括號(hào)高于棧頂左括號(hào)與棧頂比較直接入棧括號(hào)類型低于棧頂直接入棧右括號(hào)取出棧頂兩個(gè)從棧中取出操作符放入數(shù)作相應(yīng)計(jì)算數(shù)組結(jié)果存入數(shù)棧YESNO丟棄（是否為（將數(shù)值棧棧空符號(hào)棧是棧非空2 個(gè)數(shù)計(jì)算，頂返回否為空結(jié)果存入數(shù)值棧4 直接計(jì)算中綴表達(dá)式算法流程圖.三、源代碼下面給出的是用先轉(zhuǎn)后綴再計(jì)算和直接計(jì)算的算法實(shí)現(xiàn)的程序的源代碼： #include/*導(dǎo)入需要用到的各種包*/ #include#includetypedef struct/*定義結(jié)構(gòu)體用來存儲(chǔ)操作符*/char op;/*存儲(chǔ)字符*/int level;/*存儲(chǔ)優(yōu)先級(jí)*

5、/OpNode; typedefstructOpNode op100;int top;int size;/*表示棧內(nèi)元素的個(gè)數(shù)*/ stack;/*定義符號(hào)棧*/void init(stack *st)/*初始化棧*/st-size=0;st-top=0;OpNodepop(stack *a)/ *出棧*/if (a-size=0)/*假如棧為空結(jié)束操作*/exit(-1);a-size-;return a-op-(a-top);/*取出棧頂元素*/void push(stack *a,OpNode op)/*入棧函數(shù)*/a-size+;a-op(a-top)+=op;OpNode top(s

6、tack *a)/*觀看棧頂函數(shù)*/if (a-size=0)/*假如棧為空結(jié)束操作*/printf(stack is emptyn);exit(-1);return a-op(a-top)-1;/*只得到棧頂?shù)闹刀怀鰲?/.typedef struct/*定義數(shù)值棧*/double num100;int top;/*棧頂指針*/int size; numstack;void init2(numstack *st)/*初始化數(shù)值棧*/st-size=0;st-top=0;doublepop2(numstack *a)/*數(shù)值棧出棧*/if (a-size=0)/*出棧前的判空*/exit(-

7、1);a-size-;return a-num-(a-top);/*得到棧頂?shù)闹?/void push2(numstack *a,double num)/*入棧*/a-size+;a-num(a-top)+=num;voidmain()/*主函數(shù)*/void change (char str,char exp);/*聲明要用到的各個(gè)函數(shù)*/ double CalResult(char exp);/*聲明后綴表達(dá)式的計(jì)算函數(shù)*/double Directcalresult(char str);int check(char str,char chestr100);char str100,exp10

8、0,chestr100;存儲(chǔ)對應(yīng)的達(dá)式為:n);gets(str);if(check(str,chestr)/*調(diào)用容錯(cuò)函數(shù)*/n);printf(%sn,str);printf(chestr);/*依據(jù)輸入狀況指出錯(cuò)誤的地方*/exit(-1);.change(str,exp);/*調(diào)用函數(shù)將中綴轉(zhuǎn)化為后綴*/printf(后綴表達(dá)式為:%sn,exp);printf(運(yùn)算結(jié)果為：%fn,CalResult(exp);/*調(diào)用函數(shù)計(jì)算后綴表達(dá)式*/ printf(直接運(yùn)算的結(jié)果為:%fn,Directcalresult(str);/*調(diào)用直接計(jì)算函數(shù)*/void change (char s

9、tr,char ch)/*將前綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式*/int i=0;/*str*/int k=0;char c;/*字符串中取出的放在C*/stack st;/*定義符號(hào)棧*/OpNode op; OpNodeops;init(&st);/*初始化符號(hào)棧*/c=stri+;while (c!=0)/*對字符串進(jìn)行掃描*/if ( (c=0&c=0&c0)/*再次檢查棧是否為空，*/op=top(&st);elsebreak;/*為空就結(jié)束*/pop(&st);/*去掉左括號(hào)*/.if (c=+|c=-)/*假如是+-號(hào)*/op.op=c;op.level=1;if (st.size=0)

10、elsepush(&st,op);/*假如此時(shí)棧為空直接入棧*/ops=top(&st);/*觀看棧頂*/while (ops.level=op.level)/*假如棧頂優(yōu)先級(jí)高*/ops=pop(&st);chk+=ops.op;/*將棧頂元素取出存入數(shù)組中*/if (st.size0)ops=top(&st);/*進(jìn)行判空操作，棧為空結(jié)束*/elsebreak;push(&st,op);/*此時(shí)棧頂優(yōu)先級(jí)低，入棧*/if(c=*|c=/|c=%)/*假如是*/進(jìn)行*/op.op=c;op.level=2;if (st.size=0)push(&st,op);/*假如此時(shí)棧為空直接入棧*/e

11、lseops=top(&st);/*觀看棧頂*/while (ops.level=op.level)/*假如棧頂優(yōu)先級(jí)高*/ops=pop(&st);/*將棧頂元素取出存入數(shù)組中*/chk+=ops.op;if (st.size0)ops=top(&st);/*進(jìn)行判空操作，棧為空結(jié)束*/elsebreak;.push(&st,op);/*此時(shí)棧頂優(yōu)先級(jí)低，入棧*/c=stri+;/*索引自加檢索下一個(gè)字符*/while(st.size!=0)/*最終推斷棧假如不為空*/ops=pop(&st);/*取出棧內(nèi)元素存入數(shù)組中*/chk+=ops.op;chk=0;/*將0*/double Cal

12、Result(char exp)/*后綴表達(dá)式的計(jì)算*/char c;numstack numst;/*建立數(shù)值棧*/double d1,d2,dr;int k=0;/*后綴表達(dá)式的索引*/int i=0;char*s;/*將字符轉(zhuǎn)化為浮點(diǎn)數(shù)的索引*/char trans100;/*存字符表示的一段數(shù)字*/init2 (&numst);/*實(shí)現(xiàn)數(shù)值棧*/c=expk+;while (c!=0)/*開頭掃描后綴表達(dá)式*/if(c=+|c=-|c=*|c=/|c=%)/*假如是操作符*/switch(c)case + :/*假如是加法操作*/d2=pop2(&numst);d1=pop2(&num

13、st);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=d1*d2;相乘后入棧*/push2(&numst,dr);break;case / :/*假如是除法操作*/d2=pop2(&numst);d1=pop2(&numst);dr=d1/d2;相除后入棧*/push2(&nu

14、mst,dr);break;case % :/*假如是取余操作*/d2=pop2(&numst);d1=pop2(&numst);dr=(double)(int)d1%(int)d2);/*類型轉(zhuǎn)化并取余后入棧*/push2(&numst,dr);break;if (c=0&c=0&c=9|c=.)transi+=c;/*將字符存入數(shù)組進(jìn)行下一個(gè)的掃描*/c=expk+;transi+=0;/*將表示數(shù)字的字符串結(jié)束*/i=0;s=trans;/*將指針指向該數(shù)組*/d1=atof(s);/*利用函數(shù)將字符串轉(zhuǎn)化為浮點(diǎn)數(shù)*/push2(&numst,d1);c=expk+;return pop

15、2(&numst);/*最終結(jié)果將在數(shù)值棧中，取出作為返回值*/double Directcalresult(char str)/*表達(dá)式的直接計(jì)算出結(jié)果*/stack ms;/*建立符號(hào)棧*/numstack mns;/*建立數(shù)值棧*/double calculate(double od1,double od2,OpNode op); int index=0;/*str的索引*/int len=strlen(str);char c;char trans100;/*存放數(shù)值的一段字符*/int i=0;*/.char * s;doubled;OpNode tempn;/*存放當(dāng)前掃描的操作符*

16、/OpNode templn;double oda,odb,odr;double result;/*作為返回值返回結(jié)果*/init (&ms);/*實(shí)現(xiàn)兩個(gè)棧*/init2(&mns);while(index=0&c=0&c=tempn.level)/*棧頂優(yōu)先級(jí)高*/templn=pop(&ms);取出操作數(shù)和操作符計(jì)算*/odb=pop2(&mns);oda=pop2(&mns); odr=calculate(oda,odb,templn);push2(&mns,odr);結(jié)算結(jié)果入棧*/if(ms.size0).templn=top(&ms);/*假如?？战Y(jié)束*/elsebreak;pu

17、sh(&ms,tempn);/*操作符入棧*/if(c=*|c=/|c=%)/*假如是*/%操作*/tempn.level=2;tempn.op=c;if(ms.size=0)push(&ms,tempn);/*?？罩苯尤霔?/elsetempln=top(&ms);while (templn.level=tempn.level)/*棧頂優(yōu)先級(jí)高*/templn=pop(&ms);/*取出操作數(shù)和操作符計(jì)算*/odb=pop2(&mns);oda=pop2(&mns); odr=calculate(oda,odb,templn);push2(&mns,odr);/*結(jié)算結(jié)果入棧*/if(ms.

18、size0)templn=top(&ms);elsebreak;/*假如?？战Y(jié)束*/templn=top(&ms);push(&ms,tempn);/*操作符入棧*/if(c=()/*假如是左括號(hào)*/tempn.level=-1;tempn.op=c;/*直接入棧優(yōu)先級(jí)定位-1*/push(&ms,tempn);if(c=)/*假如是右括號(hào)*/.while(tempn.op!=()/*遇到左括號(hào)結(jié)束*/templn=pop(&ms);odb=pop2(&mns);/*從數(shù)棧中取兩個(gè)數(shù)，從符號(hào)棧里取操作符*/oda=pop2(&mns);odr=calculate(oda,odb,templn)

19、;/*計(jì)算出結(jié)果入棧*/push2(&mns,odr);if (ms.size0)tempn=top(&ms);elsebreak;/*假如?？战Y(jié)束*/pop(&ms);/*取出左括號(hào)*/tempn=top(&ms);while(1)templn=pop(&ms);odb=pop2(&mns);/*從數(shù)棧中取兩個(gè)數(shù)，從符號(hào)棧里取操作符*/oda=pop2(&mns);odr=calculate(oda,odb,templn);/*計(jì)算出結(jié)果入棧*/push2(&mns,odr);if (ms.size0)tempn=top(&ms);/*假如?？战Y(jié)束*/elsebreak;result =po

20、p2(&mns);/*最終的結(jié)果在數(shù)值棧中返回*/return result;double calculate(double od1,double od2,OpNode op)/*/switch(op.op)case + : return od1+od2;case - : return od1-od2;/*推斷操作符是哪個(gè)執(zhí)行相應(yīng)計(jì)算*/case * : return od1*od2;case / : return od1/od2;case % : return (double)(int)od1%(int)od2);return 0;/*0*/.int check(char str,char

21、chestr100)/*容錯(cuò)函數(shù)*/char c;char cdivide;int i=0;/*str*/stack che;*/OpNode temp;int k=0;*/int isinteger(char integer100);/*%計(jì)算是推斷是否是整數(shù)*/char s110;/*%操作時(shí)存儲(chǔ)%左右的數(shù)字*/char s210;intindexs1=0;int indexs2=0;init (&che);int flag=0;*/int tag=0;c=stri;/*開頭掃描*/int j;/*數(shù)組chestr*/for(j=0;j0)pop(&che);/*棧不為空就取出一個(gè)左括號(hào)*

22、/elseflag=1;printf(缺少左括號(hào)n);/*否則提示有錯(cuò)*/ chestri=;右括號(hào)下加*/.if(c=/)/*0*/*/j=0;cdivide=stri+1+j;/*取出除號(hào)后的數(shù)*/ while(cdivide=0&cdivide=0&stri-indexs1-1=0&stri+indexs2+10)/*假如最終棧不為空*/printf(缺少右括號(hào)n);/*棧中還有沒配對的左括號(hào)報(bào)錯(cuò)*/return flag;/*返回是否有錯(cuò)*/int isinteger(char integer100)/*推斷數(shù)組內(nèi)是否是整數(shù)*/int i=0;/*傳過來的數(shù)組的索引*/char c;

23、c=integeri+;while(c!=0)/*直到字符串最終掃描結(jié)束*/if(c=.)/*只要有一個(gè)字符為小數(shù)點(diǎn)就不是整數(shù)*/return 1;elsec=integeri+;/*掃描下一個(gè)*/return 0;四、運(yùn)行結(jié)果在輸入表達(dá)式?jīng)]有錯(cuò)誤的狀況下，可以得到兩種算法的運(yùn)算結(jié)果為：. .算術(shù)表達(dá)式為：算術(shù)表達(dá)式為：6+(5-6*9+8/2.1)-9%7后綴表式為61516191* - 8 1 2. l l / 91 71%運(yùn)算結(jié)果為： 41. 190476直接運(yùn)算的結(jié)果為： 41190476ress any key tocontinue式5 表達(dá)式正確時(shí)兩種算法運(yùn)行結(jié)果圖假如表達(dá)式的輸入有錯(cuò)誤，運(yùn)行結(jié)果分別如下：0算術(shù)表達(dá)式為：算術(shù)表達(dá)式為：6