北工大數(shù)據(jù)結構第二次上機中綴轉后綴實驗報告

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

2、綴表達式，用棧來存放表達式中的操作數(shù)，開括號，以及在這個開括號后面的其他暫時不能確定計算次序的內容。（1）當輸入的是操作數(shù)時，直接輸出到后綴表達式（2）當遇到開括號時，將其入棧（3）當輸入遇到閉括號時，先判斷棧是否為空，若為空，則表示括號不匹配，應作為錯誤異常處理，清棧退出。若非空，則把棧中元素依次彈出，直到遇到第一個開括號為止，將彈出的元素輸出到后綴表達式序列中。由于后綴表達式不需要括號，因此彈出的括號不放到輸出序列中，若沒有遇到開括號，說明括號不匹配，做異常處理，清棧退出。（4）當輸入為運算符時（四則運算+-*/之一）時：a.循環(huán)，當（棧非空&&棧頂不是開括號&&a

3、mp;棧頂運算符的優(yōu)先級不低于輸入的運算符的優(yōu)先級）時，反復操作將棧頂元素彈出，放到后綴表達式中。b.將輸入的運算符壓入棧中。（5）最后，當中綴表達式的符號全部掃描完畢時，若棧內仍有元素，則將其全部依次彈出，放在后綴表達式序列的尾部。若在彈出的元素中遇到開括號，則說明括號不匹配，做異常處理，清棧退出。B.實現(xiàn)#include<stdio.h>#include<string.h>#include<stdlib.h>#include<stack>usingnamespacestd;defineN1000charinfixN;中綴表達式（未分離，都在一

4、個字符串里）charexpressionN10;保存預處理過的表達式，也就是每個元素都分離'a'&&x<='z')|,用字符串數(shù)組過的表達式charsuffixN10;保存后綴表達式的操作數(shù)intcount;/表達式中元素的個數(shù)（一個完整到數(shù)字（可能不止一位數(shù)）或者符號）intsuffixLength;/后綴表達式的長度intlevel(chara)switch(a)case'#':return0;case'+':case'-':return1;case'*':case'

5、;/':return2;case'A':return3;default:break;return-1;intisDigital(charx)if(x>='0'&&xv=9)|(x>='A'&&xv=Z)|(x>(x='.')return1;return0;intisNumber(char*str)inti;for(i=0;stri;i+)if(isDigital(stri)=0)return0;return1;產*預處理中綴表達式，把連續(xù)的字符分離成不同的元素（expres

6、sion口）保存，方便后面的計算，因為這里考慮了運算數(shù)可能不全是個位數(shù)比如：(12+3)在處理成后綴表達式時，是123+,容易產生歧義(1+23?12+3)*/voidpretreatment(char*str)inti,j,numberFlag;chartemp3;charnumber10;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!='&#

7、39;)temp0=stri;temp1=0;strcpy(expressioncount+,temp);elsenumberFlag=1;numberj+=stri;puts("分離后的表達式為");for(i=0;i<count;i+)printf("%s",expressioni);puts("");puts("");產*中綴表達式轉后綴表達式遍歷字符串，對于stristri是運算數(shù)(或者是字母代替的運算變量)輸出；stri是符號，有兩種情況(1),是右括號，棧頂元素輸出，直到與stri匹配的左括號出棧

8、(左括號不用輸出打印)(2),是運算符，判斷stri與棧頂元素的優(yōu)先級，stri優(yōu)先級不高于棧頂符號，則棧頂元素輸出，直到棧空或者棧頂符號優(yōu)先級低于stri*/voidin巾x_to_suffix(charstrN10)memset(sufix,0,sizeof(suffix);suffixLength=0;stack<char*>st;inti=0;charMark2="#"st.push(Mark);doif(isNumber(stri)=1)運算數(shù)直接保存到后綴表達式中strcpy(suffixsufixLength+,stri);elseif(stri0

9、='(')/是左括號，直接入棧st.push(stri);elseif(stri0=')')是右括號，棧頂出棧，直到與其匹配的左括號出棧while(strcmp(st.top(),"(")!=0)chartemp10;strcpy(temp,st.top();strcpy(suffixsuffixLength+,temp);st.pop();st.pop();elseif(strcmp(st.top(),"(")=0)/是運算符，且棧頂是左括號，則該運算符直接入棧st.push(stri);else是運算符，且棧頂元素優(yōu)先

10、級不小于運算符，則棧頂元素一直出棧，直到棧空或者遇到一個優(yōu)先級低于該運算符的元素while(!st.empty()chartemp10;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)將棧取空結束chartemp10;strcpy(temp,st.top();strcpy(suffixsuffixL

11、ength+,temp);st.pop();)puts("后綴表達式為；for(i=0;i<suffixLength;i+)printfsuffixi);puts(");puts(”)；)*計算后綴表達式的值*/charktN10;intstackTop;voidgetResult(charstrN10)stackTop=0;/*這里要注意，內存的分配方案導致i的位置就在temp9旁邊，然后strcpy()函數(shù)直接拷貝內存的話，在temp越界情況下會覆蓋i的值*/inti;chartemp10;for(i=0;i<suffixLength;i+)if(isNum

12、ber(stri)=1)strcpy(ktstackTop+,stri);elsechara10,b10;doublena,nb,nc;strcpy(a,ktstackTop-1);na=atof(a);stackTop-;strcpy(b,ktstackTop-1);nb=atof(b);stackTop-;if(stri0='+')nc=nb+na;elseif(stri0='-')nc=nb-na;elseif(stri0='*')nc=nb*na;elseif(stri0='/')nc=nb/na;sprintf(temp

13、,"%lf",nc);strcpy(ktstackTop+,temp);puts("nTheresultis:%fn");printf("%sn",ktstackTop-1);intmain()printf("PleaseinputcalculateExpression:n");chartempN;while(gets(infix)strcpy(temp,infix);pretreatment(strcat(temp,"");infix_to_suffix(expression);getResult(su