C棧實現將中綴表達式轉換為后綴表達式_第1頁
C棧實現將中綴表達式轉換為后綴表達式_第2頁
C棧實現將中綴表達式轉換為后綴表達式_第3頁
全文預覽已結束

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、5將中綴表達式轉換為后綴表達式【問題才茁述】表達式轉換。輸入的中綴表達式為字符串,轉換得到的后綴表達式存入字符數組中并輸出。例如:a*(x+y)/(b-x)轉換后得:axy+*bx-/【數據結構】定義一個暫時存放運算符的轉換工作棧opst。中綴表達式字符串char*infix;后綴表達式字符串char*postfix;【算法提示】轉換規則:把運算符移到它的兩個操作數后面,刪除掉所有的括號。從頭到尾掃描中綴表達式,對不同類型的字符按不同情況處理:數字或小數點,直接寫入字符串postfix,并在每個數值后面寫入一個空格;左括號,進棧,直到遇見相配的右括號,才出棧;右括號,表明已掃描過括號內的中綴表

2、達式,把從棧頂直到對應左括號之間的運算符依次退棧,并把結果推入棧內;對于運算符,分兩種情況處理:該運算符的優先級大于棧頂符號的優先級,則入棧;若該運算符的優先級小于棧頂優先級,則先彈出棧頂運算符、寫入postfix串;繼續將該運算符與棧頂運算符比較,直到能把它推入棧內為止(即優先級大于棧頂運算符)。說明:自行設計運算符優先級的表示。【主要代碼】#include<assert.h>#include<iostream.h>/#include<stdlib.h>constintstackIncreament=20;classSeqStackprivate:char

3、*elements;inttop;intmaxSize;voidoverflowProcess();public:SeqStack(intsz=50);SeqStack()deleteelements;voidPush(constchar&x);boolPop(char&x);boolgetTop(char&x);intisdigit(charch);intisp(charchi);inticp(charch2);boolIsEmpty()constreturn(top=-1)?true:false;boolIsFull()constreturn(top=maxSize

4、-1)?true:false;intgetSize()constreturntop+1;voidMakeEmpty()top=-1;SeqStack:SeqStack(intsz)top=-1;maxSize=sz;elements=newcharmaxSize;assert(elements!=NULL);voidSeqStack:overflowProcess()(char*newArray=newcharmaxSize+stackIncreament;/*if(newArray=NULL)'cerr<<”存儲分配失敗!"<<endl;exit(1

5、);*/for(inti=0;i<=top;i+)newArrayi=elementsi;maxSize=maxSize+stackIncreament;deleteelements;elements=newArray;voidSeqStack:Push(constchar&x)(if(IsFull()=true)overflowProcess();elements+top=x;boolSeqStack:Pop(char&x)(if(IsEmpty()=true)returnfalse;x=elementstop-;returntrue;boolSeqStack:getT

6、op(char&x)(if(IsEmpty()=true)returnfalse;x=elementstop;returntrue;intSeqStack:isdigit(charch)(if(ch>='0'&&ch<='9'|ch='.'|ch>='a'&&ch<='z'|ch>='A'&&ch<='Z')return1;elsereturn0;intSeqStack:isp(charch1

7、)(intval;switch(ch1)(case'#':val=0;break;case'(':val=1;break;case'*':case'/':case'%':val=5;break;case'+':case'-':val=3;break;case')':val=6;break;returnval;intSeqStack:icp(charch2)(intval;switch(ch2)(case'#':val=0;break;case'

8、(':val=6;break;case'*':case'/':case'%':val=4;break;case'+':case'-':val=2;break;case')':val=1;break;returnval;classShow:publicSeqStack(public:Show(intsz):opst(sz)(voidClear();voidPostfix();voidInput();voidOutput();private:SeqStackopst;char*infix;cha

9、r*postfix;voidShow:Clear()(opst.MakeEmpty();voidShow:Input()(infix=newchar20;cout<<"請輸入中綴表達式:"<<endl;cin>>infix;voidShow:Postfix()(postfix=newchar20;cout<<"輸出的后綴表達式為:"<<endl;SeqStackopst;charch='#',ch1,op;opst.Push(ch);inti=0;ch=infixi;while(

10、opst.IsEmpty()=false&&ch!='#')if(opst.isdigit(ch)=1)(cout<<ch;i+;ch=infixi;elsecout<<""opst.getTop(ch1);if(opst.isp(ch1)<opst.icp(ch)opst.Push(ch);i+;ch=infixi;elseif(opst.isp(ch1)>opst.icp(ch)opst.Pop(op);if(op!='#')cout<<op;elseopst.Pop(op)

11、;i+;ch=infixi;cout<<endl;voidmain()ShowSh(100);Sh.Input();Sh.Postfix();【實驗過程】請輸入市綴表達式:(l+2)*3+a-c/6輸出的后綴表達式為:12+3*a+c6/-PressanykeytocontinueI""方感'f«.'fS.st.泓.p象.中,a,rtfa-4其L普44位亶15.L1半5行23圳W中文(中皿財【實驗體會】一直都不理解為什么要加語句"if(newArray=NULL)cerr<<"存儲分配失敗!"<<endl;exit(1);*/”覺得此舉可有可無,到現在為止去掉了

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論