北工大數(shù)據(jù)結(jié)構(gòu)第二次上機(jī)中綴轉(zhuǎn)后綴實(shí)驗(yàn)報(bào)告

1、北工大數(shù)據(jù)結(jié)構(gòu)第二次上機(jī)中 綴轉(zhuǎn)后綴實(shí)驗(yàn)報(bào)告北京工業(yè)大學(xué)2016- 2017 學(xué)年 第 學(xué)期信息學(xué)部計(jì)算機(jī)學(xué)院課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法報(bào)告性質(zhì)：作業(yè)報(bào)告，口實(shí)驗(yàn)報(bào)告學(xué)號(hào)：姓名：任課教師：蘇航課程性質(zhì)：學(xué)科基礎(chǔ)必修課學(xué)分：3.5學(xué)時(shí)：56班級(jí)：成績：小組成員：教師評(píng)語：2017年 3月 31日?qǐng)?bào)告題目：輸入中綴表達(dá)式，輸出后綴表達(dá)式，并對(duì)表達(dá)式求值A(chǔ).分析中綴表達(dá)式的運(yùn)算順序受運(yùn)算符優(yōu)先級(jí)和括號(hào)的影響。因此，將中綴 表達(dá)式轉(zhuǎn)換成等價(jià)的后綴表達(dá)式的關(guān)鍵在于如何恰當(dāng)?shù)娜サ糁芯Y表達(dá)式 中的括號(hào)，然后在必要時(shí)按照先乘除后加減的優(yōu)先規(guī)則調(diào)換運(yùn)算符的先后 次序。在去括號(hào)的過程中用棧來儲(chǔ)存有關(guān)的元素。容。(1

2、)(2)(3)基本思路：從左至右順序掃描中綴表達(dá)式，用棧來存放表達(dá)式中的操 作數(shù)，開括號(hào)，以及在這個(gè)開括號(hào)后面的其他暫時(shí)不能確定計(jì)算次序的內(nèi)當(dāng)輸入的是操作數(shù)時(shí)，直接輸出到后綴表達(dá)式當(dāng)遇到開括號(hào)時(shí)，將其入棧當(dāng)輸入遇到閉括號(hào)時(shí)，先判斷棧是否為空，若為空，則表示括號(hào)不匹 配，應(yīng)作為錯(cuò)誤異常處理，清棧退出。若非空，則把棧中元素依次彈 出，直到遇到第一個(gè)開括號(hào)為止，將彈出的元素輸出到后綴表達(dá)式序列中。由于后綴表達(dá)式不需要括號(hào),因此彈出的括號(hào)不放到輸出序V(4)(5)中，若沒有遇到開括號(hào)，說明括號(hào)不匹配，做異常處理，清棧退出。當(dāng)輸入為運(yùn)算符時(shí)（四則運(yùn)算+ - * / 之一）時(shí)：a.循環(huán)，當(dāng)（棧非空&娠頂不

3、是開括號(hào)&娠頂運(yùn)算符的優(yōu)先級(jí)不低于 輸入的運(yùn)算符的優(yōu)先級(jí)）時(shí)，反復(fù)操作將棧頂元素彈出，放到后綴表 達(dá)式中。b.將輸入的運(yùn)算符壓入棧中。最后，當(dāng)中綴表達(dá)式的符號(hào)全部掃描完畢時(shí)，若棧內(nèi)仍有元素，則將 其全部依次彈出，放在后綴表達(dá)式序列的尾部。若在彈出的元素中遇 到開括號(hào)，則說明括號(hào)不匹配，做異常處理，清棧退出。B.實(shí)現(xiàn)#include#include#include#includeusing namespace std;#define N 1000char infixN; /中綴表達(dá)式（未分離，都在一個(gè)字符串里）保存預(yù)處理過的表達(dá)式，也就是每個(gè)元素都分離char expressionN10;a&x

4、=0&xv=9)|(x=A&xv=Z)| (x(x=.)return 1;return 0; int isNumber(char *str)int i;for(i=0;stri;i+)if(isDigital(stri)=0)return 0;return 1;產(chǎn)*預(yù)處理中綴表達(dá)式，把連續(xù)的字符分離成不同的元素（expression口）保存，方便后面的計(jì)算，因?yàn)檫@里考慮了運(yùn)算數(shù)可能不全是個(gè)位數(shù)比如：(12+3)在處理成后綴表達(dá)式時(shí)，是123+,容易產(chǎn)生歧義(1+23 ? 12+3)*/void pretreatment(char *str)int i,j,numberFlag;char tem

5、p3;char number10;count=0;numberFlag=0;for(j=0,i=0;stri;i+)if(isDigital(stri)=0)if(numberFlag=1)numberj=0;strcpy(expressioncount+,number);j=0；numberFlag=0;if(stri!= )temp0=stri;temp1=0;strcpy(expressioncount+,temp);else numberFlag=1;numberj+=stri;puts(分離后的表達(dá)式為);for(i=0;icount;i+)printf(%s ,expression

6、i);puts();puts();產(chǎn)*中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式 遍歷字符串，對(duì)于stristri是運(yùn)算數(shù)(或者是字母代替的運(yùn)算變量)輸出;(1),是右括 輸出打印)stri是符號(hào)，有兩種情況棧頂元素輸出，直到與 stri匹配的左括號(hào)出棧(左括號(hào)不用(2),是運(yùn)算符，判斷stri與棧頂元素的優(yōu)先級(jí)，stri優(yōu)先級(jí) 不高于 棧頂 符號(hào)，則棧頂元素輸出，直到?？栈蛘邨ｍ敺?hào)優(yōu)先級(jí)低于stri*/ void in巾x_to_suffix(char strN10)memset(sufix,0,sizeof(suffix);suffixLength=0;stack st;int i=0;char Mark2

7、=#;st.push(Mark);do運(yùn)算數(shù)直接保存到后綴表達(dá)式中if(isNumber(stri)=1)/strcpy(suffixsufixLength+,stri);else if(stri0=()st.push(stri);else if(stri0=) 其匹配的左括號(hào)出棧/是左括號(hào)，直接入棧是右括號(hào)，棧頂出棧，直到while( strcmp(st.top(),()!=0)char temp10;strcpy(temp,st.top();strcpy(suffixsuffixLength+,temp); st.pop();st.pop(); elseif( strcmp(st.top(

8、),()=0)/是運(yùn)算符，且棧頂是左括號(hào),則該運(yùn)算符直接入棧st.push(stri);else /是運(yùn)算符，且棧頂元素優(yōu)先級(jí)不小于運(yùn)算符，則棧頂元素一直/出棧，直到 棧空或者遇到一個(gè)優(yōu)先級(jí)低于該運(yùn)算符的元素while( !st.empty()char temp10;strcpy(temp,st.top();if( level(stri0) level(temp0)break;strcpy(suffixsuffixLength+,temp);st.pop()；st.push(stri);i+;while(stri0!=0);while( strcmp(st.top(),#)!=0 )/將棧取空

9、結(jié)束char temp10;strcpy(temp,st.top();strcpy(suffixsuffixLength+,temp);st.pop();puts(后綴表達(dá)式為：)；for(i=0;isuffixLength;i+)printf(%s,suffixi);puts();puts();產(chǎn)*計(jì)算后綴表達(dá)式的值* char ktN10;int stackTop;void getResult(char strN10)stackTop=0;/*這里要注意，內(nèi)存的分配方案導(dǎo)致i的位置就在temp9旁邊，然后strcpy() 函數(shù)直接拷貝內(nèi)存的話，在temp越界情況下會(huì)覆蓋i的值*/int i

10、;char temp10;for(i=0;isuffixLength;i+)if(isNumber(stri)=1)strcpy(ktstackTop+,stri);else char a10,b10;double na,nb,nc;strcpy(a,ktstackTop-1);na = atof(a);stackTop-;strcpy(b,ktstackTop-1);nb = atof(b);stackTop-;if(stri0=+)nc=nb+na;else if(stri0=-)nc=nb-na;else if(stri0=*)nc=nb*na;else if(stri0=/)nc=nb

11、/na;sprintf(temp,%lf,nc);strcpy(ktstackTop+,temp);puts(nThe result is : %fn);printf(%sn,ktstackTop-1);int main()printf(Please input calculate Expression :n);char tempN;while(gets(infix)strcpy(temp,infix);pretreatment( strcat(temp,); infix_to_suffix(expression); getResult(suffix);return 0;C.總結(jié)實(shí)驗(yàn)需要細(xì)心細(xì)心再細(xì)心。