數(shù)據(jù)結構筆記分享-波蘭表達式

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