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

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

2、到字符串中，然后再次檢查棧頂，直到棧中元素的優(yōu)先級(jí)低于掃描操作符，則此操作符入棧，然后掃描下一個(gè)字符，直到遇到字符串的結(jié)束符號(hào)0，掃描結(jié)束。數(shù)組中存的就是后綴表達(dá)式。得到后綴表達(dá)式后，進(jìn)行計(jì)算，要用到數(shù)值棧。首先要將字符表示的數(shù)字轉(zhuǎn)化為浮點(diǎn)小數(shù)，然后進(jìn)行掃描，遇到數(shù)值，放入棧中，遇到操作符，就從棧中取出兩個(gè)數(shù)，進(jìn)行計(jì)算后再放入棧中，掃描下一個(gè)，最后的計(jì)算結(jié)果就存到了棧中，直接取出棧內(nèi)元素，就是計(jì)算的最后結(jié)果。第二種算發(fā)首先要建立兩個(gè)棧，一個(gè)用來存放操作符，一個(gè)用來存放數(shù)值。開始對(duì)用戶輸入的字符串進(jìn)行掃描，如果是數(shù)字字符或者小數(shù)點(diǎn)，則將字符轉(zhuǎn)化為浮點(diǎn)數(shù)存到數(shù)棧里，如果是操作符，則觀察符號(hào)棧，如果

3、棧頂元素的優(yōu)先級(jí)低于觀察的操作符，則操作符入棧，如果棧頂元素的優(yōu)先級(jí)高于或者等于觀察的操作符，則從數(shù)值棧中取出兩個(gè)浮點(diǎn)數(shù)，從符號(hào)棧中取出棧頂?shù)牟僮鞣?，然后進(jìn)行相應(yīng)的數(shù)值計(jì)算，所得的結(jié)果再存到數(shù)值棧中，重復(fù)這樣的操作，直到符號(hào)棧中棧頂元素的優(yōu)先級(jí)低于觀察的操作符，則此操作符入棧，然后對(duì)下一個(gè)字符進(jìn)行掃描。如果是左括號(hào)，則不進(jìn)行優(yōu)先級(jí)的比較，直接入棧，入棧后優(yōu)先級(jí)為-1。如果是右括號(hào)，則從數(shù)值棧中取兩個(gè)操作數(shù)，符號(hào)棧中取出一個(gè)符號(hào)，然后進(jìn)行計(jì)算后得數(shù)放入數(shù)棧中，不斷進(jìn)行此類操作，直到從棧中取出的是左括號(hào)為止，左括號(hào)去掉，掃描下一個(gè)。掃描結(jié)束后，計(jì)算也結(jié)束了，計(jì)算的結(jié)果就存放在數(shù)值棧中，最后把數(shù)值棧

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

5、式的主要流程為：取得字符并判斷如果是數(shù)字或小數(shù)點(diǎn)直接放入字符數(shù)組中在其后加入分隔符如果是操作符與棧頂比較判斷哪類括號(hào)直接入棧右括號(hào)取出不為(從棧中取出操作符放入數(shù)組直接入棧優(yōu)先級(jí)高于棧頂如果是括號(hào)出棧存入數(shù)組中左括號(hào)優(yōu)先級(jí)不高于棧頂圖2 中綴轉(zhuǎn)化為后綴算法流程圖后綴表達(dá)式的計(jì)算，實(shí)現(xiàn)的流程圖為：從數(shù)棧取2個(gè)數(shù)做相應(yīng)計(jì)算結(jié)果存入數(shù)棧判斷符號(hào)類型得到后綴表達(dá)式數(shù)字字符操作符轉(zhuǎn)化為浮點(diǎn)數(shù)入棧從數(shù)棧中取出計(jì)算結(jié)果作為返回值圖3 后綴表達(dá)式計(jì)算算法流程圖下面介紹直接計(jì)算出結(jié)果的算法的實(shí)現(xiàn)：棧非空棧空低于棧頂高于棧頂NOYES左括號(hào)得到中綴表達(dá)式從字符串中取出一個(gè)字符判斷字符類型數(shù)字字符操作符轉(zhuǎn)化為浮點(diǎn)數(shù)

6、入棧括號(hào)括號(hào)類型直接入棧右括號(hào)從棧中取出操作符是否為（丟棄（放入數(shù)組與棧頂比較直接入棧取出棧頂兩個(gè)數(shù)作相應(yīng)計(jì)算結(jié)果存入數(shù)棧符號(hào)棧是否為空將數(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í)*/OpNode;typedef struct OpNode op100; int top;

7、int size; /*表示棧內(nèi)元素的個(gè)數(shù)*/ stack; /*定義符號(hào)棧*/void init(stack *st) /*初始化棧*/ st-size=0; st-top=0;OpNode pop(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(stack *a) /*觀察棧頂函數(shù)*/ if (a-s

8、ize=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;double pop2(numstack *a) /*數(shù)值棧出棧*/ if (a-size=0) /*出棧前的判空*/ exit(-1); a-si

9、ze-; return a-num-(a-top); /*得到棧頂?shù)闹?/void push2(numstack *a,double num) /*入棧*/ a-size+; a-num(a-top)+=num;void main() /*主函數(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

10、,exp100,chestr100; /*str存儲(chǔ)原算術(shù)表達(dá)式，exp存儲(chǔ)對(duì)應(yīng)的 printf(算術(shù)表達(dá)式為:n); 后綴表達(dá)式,chestr存儲(chǔ)容錯(cuò)字符*/ gets(str); if(check(str,chestr) /*調(diào)用容錯(cuò)函數(shù)*/ printf(表達(dá)式錯(cuò)在：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ù)

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

12、t); else break; /*為空就結(jié)束*/pop(&st); /*去掉左括號(hào)*/if (c=+|c=-) /*如果是+-號(hào)*/ op.op=c;op.level=1; /*優(yōu)先級(jí)為1*/ if (st.size=0)push(&st,op); /*如果此時(shí)棧為空直接入棧*/else 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é)束*/ els

13、e break; push(&st,op); /*此時(shí)棧頂優(yōu)先級(jí)低，入棧*/if(c=*|c=/|c=%) /*如果是*/進(jìn)行*/op.op=c; op.level=2; /*優(yōu)先級(jí)為1*/ if (st.size=0)push(&st,op); /*如果此時(shí)棧為空直接入棧*/else ops=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é)束*/ else

14、break;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作為結(jié)尾存入數(shù)組*/double CalResult(char exp) /*后綴表達(dá)式的計(jì)算*/ char c; numstack numst; /*建立數(shù)值棧*/ double d1,d2,dr; int k=0; /*后綴表達(dá)式的索引*/ int i=0; /*將字符轉(zhuǎn)化為浮點(diǎn)數(shù)的索引*/ char *

15、s; 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(&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); /*類型轉(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 pop2(&numst); /*最后結(jié)果將在數(shù)值棧中，取出作為返回值*/double Directcalresult(ch

18、ar 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; /*trans的索引*/ char * s; double d; OpNode tempn; /*存放當(dāng)前掃描的操作符*/ OpNode templn; double oda,od

19、b,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é)束*/ else break; push(&ms

20、,tempn); /*操作符入棧*/ if(c=*|c=/|c=%) /*如果是*/%操作*/ tempn.level=2; /*定義優(yōu)先級(jí)為2*/ tempn.op=c; if(ms.size=0) push(&ms,tempn); /*?？罩苯尤霔?/ else templn=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(&mn

21、s,odr); /*結(jié)算結(jié)果入棧*/ if(ms.size0) templn=top(&ms); else break; /*如果?？战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)棧里取操作符*/

22、 oda=pop2(&mns); odr=calculate(oda,odb,templn); /*計(jì)算出結(jié)果入棧*/ push2(&mns,odr); if (ms.size0) tempn=top(&ms); else break; /*如果?？战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

23、,odr); if (ms.size0)tempn=top(&ms); /*如果?？战Y(jié)束*/ else break; result =pop2(&mns); /*最后的結(jié)果在數(shù)值棧中返回*/ return result;double calculate(double od1,double od2,OpNode op) /*已知操作符和操作數(shù)的計(jì)算*/ switch(op.op) case + : return od1+od2; case - : return od1-od2; /*判斷操作符是哪個(gè)執(zhí)行相應(yīng)計(jì)算*/ case * : return od1*od2; case / : return

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

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

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

27、描下一個(gè)*/return 0;4、 運(yùn)行結(jié)果在輸入表達(dá)式?jīng)]有錯(cuò)誤的情況下，可以得到兩種算法的運(yùn)算結(jié)果為：圖5 表達(dá)式正確時(shí)兩種算法運(yùn)行結(jié)果圖如果表達(dá)式的輸入有錯(cuò)誤，運(yùn)行結(jié)果分別如下：1.除數(shù)為0圖6 除數(shù)為0提示錯(cuò)誤圖2. 取余運(yùn)算操作數(shù)不為整數(shù)：圖7取余操作數(shù)不為整提示錯(cuò)誤圖3.括號(hào)匹配的問題：圖8 缺少左括號(hào)提示錯(cuò)誤圖圖9缺少右括號(hào)提示錯(cuò)誤圖五、遇到的問題及解決在編程的時(shí)候總是會(huì)有很多的意想不到的為題出現(xiàn)。這部分我主要遇到了如下兩個(gè)問題，其內(nèi)容與解決方法如下所列：l 將字符表示的數(shù)字轉(zhuǎn)化為浮點(diǎn)數(shù)這個(gè)操作的主要目的就是數(shù)字是用一串字符表示的，在計(jì)算的過程中就要把字符串轉(zhuǎn)化成對(duì)應(yīng)的浮點(diǎn)數(shù)，要解決這個(gè)問題，首