數(shù)據(jù)結(jié)構(gòu)筆記分享-波蘭表達(dá)式

數(shù)據(jù)結(jié)構(gòu)筆記分享——波蘭表達(dá)式逆波蘭表達(dá)式又叫做后綴表達(dá)式。在通常的表達(dá)式中，運(yùn)算符總是置于與之相關(guān)的兩個(gè)運(yùn)算對(duì)象之間，所以，這種表示法也稱為中綴表示。波蘭邏輯學(xué)家J.Lukasiewicz于1929年提出了另一種表示表達(dá)式的方法。按此方法，每一運(yùn)算符都置于其運(yùn)算對(duì)象之后，故稱為后綴表示。逆波蘭表達(dá)式，它的語(yǔ)法規(guī)定，表達(dá)式必須以逆波蘭表達(dá)式的方式給出。逆波蘭表達(dá)式又叫做后綴表達(dá)式。這個(gè)知識(shí)點(diǎn)在數(shù)據(jù)結(jié)構(gòu)和編譯原理這兩門課程中都有介紹，下面是一些例子：逆波蘭表達(dá)式的用途它的優(yōu)勢(shì)在于只用兩種簡(jiǎn)單操作，入棧和出棧就可以搞定任何普通表達(dá)式的運(yùn)算。其運(yùn)算方式如下：按順序掃描逆波蘭表達(dá)式，如果當(dāng)前字符為變量或者為數(shù)字，則壓棧，如果是運(yùn)算符，則將棧頂兩個(gè)元素彈出作相應(yīng)運(yùn)算，結(jié)果再入棧，最后當(dāng)表達(dá)式掃描完后，棧里的就是結(jié)果。后綴表達(dá)式求值算法:（1）從左往右順序掃描后綴表達(dá)式；（2）遇到操作數(shù)就進(jìn)棧；（3）遇到操作符就從棧中彈出兩個(gè)操作數(shù)，執(zhí)行該操作符規(guī)定的運(yùn)算；并將結(jié)果進(jìn)棧；（4）重復(fù)上述操作，直到表達(dá)式結(jié)束。彈出棧頂元素即為結(jié)果。代碼實(shí)現(xiàn)（主要是建立棧的么讓偶進(jìn)行出棧入棧操作）：#include<stdio.h>#include<malloc.h>#include<math.h>#include<string.h>#include<ctype.h>#defineM40/*定義堆棧*/typedefstruct{doubledata[M];inttop;}Stack;/*初始化堆棧*/InitStack(Stack*s){s->top=0;}/*判斷棧是否為空*/intStEmpty(Stack*s){if(s->top==0){return1;}else{return0;}}/*入棧操作*/StPush(Stack*s,doublex){if(s->top==M){printf("Thestackisoverflow!");}else{s->top=s->top+1;s->data[s->top]=x;}}/*出棧操作*/doubleStPop(Stack*s){doublet;if(!StEmpty(s)){t=s->data[s->top];s->top=s->top-1;}else{printf("StPop:Thestackisempty!");t=NULL;}returnt;}/*獲取棧頂元素*/doubleStGetTop(Stack*s){doublet;if(!StEmpty(s)){t=s->data[s->top];}else{printf("StGeTop:Thestackisempty!");t=NULL;}returnt;}/*將數(shù)字字符轉(zhuǎn)換成整形*/intChrTransferint(charc){intn;switch(c){case'0':n=0;break;case'1':n=1;break;case'2':n=2;break;case'3':n=3;break;case'4':n=4;break;case'5':n=5;break;case'6':n=6;break;case'7':n=7;break;case'8':n=8;break;case'9':n=9;break;}returnn;}/*獲取兩個(gè)操作符之間數(shù)字字符的個(gè)數(shù),返回的是最后一個(gè)數(shù)字字符的位置*/intGetNumsize(charstr[],intn1){intn2=n1;while(isdigit(str[n2])||(str[n2])==46)/*isdigit()判斷是否數(shù)字字符*/{n2=n2+1;}returnn2;}/*判斷上個(gè)函數(shù)中獲得的數(shù)字字符串中是否包含小數(shù)點(diǎn)，并返回它的位置，不包含，返回-1*/intIsIncludepoint(charstr[],intn1,intn2){intn3=-1;inti;for(i=n1;i<=n2;i++){if(str[i]=='.'){n3=i;break;}}returnn3;}/*將數(shù)字字符轉(zhuǎn)換成數(shù)值*/doubleTransfer(charstr[],intn1,intn2,intn3){doubledata=0;inti,ct;if(n3<0){for(i=n2;i>=n1;i--){ct=ChrTransferint(str[i]);data=data+ct*pow(10,n2-i);/*pow(x,y)計(jì)算x的y次方的值*/}}else{for(i=n3-1;i>=n1;i--){ct=ChrTransferint(str[i]);data=data+ct*pow(10,n3-1-i);/*pow(x,y)計(jì)算x的y次方的值*/}for(i=n3+1;i<=n2;i++){ct=ChrTransferint(str[i]);data=data+ct*pow(0.1,i-n3);/*pow(x,y)計(jì)算x的y次方的值*/}}returndata;}/*主程序*/main(){charstr[M],c;chara;intn,p1,p2,p3;/*n為字符串長(zhǎng)度，p1,p2,p3分別為數(shù)字字符起始位置，結(jié)束位置，和小數(shù)點(diǎn)位置*/doubledata;/*存放轉(zhuǎn)換后的數(shù)值*/inti=0;Stack*so=(Stack*)malloc(sizeof(Stack));/*存儲(chǔ)操作符'(':1,'+':2,'-':3,'*':4,'/':5字符'),＝'不壓棧*/Stack*sd=(Stack*)malloc(sizeof(Stack));/*存儲(chǔ)操作數(shù)*/InitStack(so);InitStack(sd);printf("Pleaseinputformula(format:(1+2)*1.2/4=):\n");n=0;while((a=getchar())!='\n'){str[n]=a;n++;}while(i<n){charc;c=str[i];if(c=='('){/*c若是'('直接入棧so，i++*/StPush(so,1);i++;}elseif(isdigit(c)){p1=i;/*c若是數(shù)字字符，一并將后面的連續(xù)數(shù)字字符轉(zhuǎn)換為數(shù)值并壓棧到sd,并把i設(shè)為后面的*/p2=GetNumsize(str,p1);p3=IsIncludepoint(str,p1,p2-1);/*第一個(gè)非數(shù)字字符的位置*/data=Transfer(str,p1,p2-1,p3);StPush(sd,data);i=p2;}elseif(c=='+'){StPush(so,2);/*c若是'+'直接入棧so,i++*/i++;}elseif(c=='-'){StPush(so,3);/*c若是'-'直接入棧so,i++*/i++;}elseif(c=='*'){if(str[i+1]=='(')/*c若是‘*’它后面的字符是否為'('，若是直接將'*'壓棧so，*/{StPush(so,4);i++;}else{doublet1,t2,t3;/*若不是，為數(shù)字字符,將后面的連續(xù)數(shù)字字符一并轉(zhuǎn)換成數(shù)值t2,sd出棧給t1,將t3=t2*t1壓棧到sd*/t1=StPop(sd);/*操作符'*'不壓棧so*/p1=i+1;p2=GetNumsize(str,p1);p3=IsIncludepoint(str,p1,p2-1);t2=Transfer(str,p1,p2-1,p3);t3=t1*t2;StPush(sd,t3);i=p2;}}elseif(c=='/'){if(str[i+1]=='('){StPush(so,5);i++;}else{doublet1,t2,t3;t1=StPop(sd);/*c是'/'同'*'*/p1=i+1;p2=GetNumsize(str,p1);p3=IsIncludepoint(str,p1,p2-1);t2=Transfer(str,p1,p2-1,p3);t3=t1/t2;StPush(sd,t3);i=p2;}}elseif(c==')'){doublet1,t2,t3;intp;while((p=StPop(so))!=1&&!StEmpty(so))/*c若是')',出棧so,判斷是'+'或'-',出棧sd兩個(gè)操作數(shù)，進(jìn)行加減運(yùn)算*/{/*直到StPop=='('*/t1=StPop(sd);t2=StPop(sd);if(p==2){t3=t2+t1;StPush(sd,t3);}elseif(p==3){t3=t2-t1;StPush(sd,t3);}}if(StGetTop(so)==4)/*然后判斷so棧頂是否為'*'或者'/'*/{StPop(so);t1=StPop(sd);/*為'*'出棧so,出棧sd獲得2個(gè)操作數(shù)，進(jìn)行乘法操作*/t2=StPop(sd);t3=t2*t1;StPush(sd,t3);}elseif(StGetTop(so)==5){StPop(so);t1=StPop(sd);/*為'/'出棧so,出棧sd獲得2個(gè)操作數(shù)，進(jìn)行除法操作*/t2=StPop(sd);t3=t2/t1;StPush(sd,t3);}i++;}elseif(c=='='){doublet1,t2,t3;/*c若是'='，這是so內(nèi)只有加減號(hào)，出棧so到p，sd到t1,t2*/intp;while(!StEmpty(so)){t1=StPop(sd);t2=StPop(s