數(shù)據(jù)結(jié)構(gòu)中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

1、中綴轉(zhuǎn)后綴，后綴求值13070319張樂2015.4.211、 需求分析明確規(guī)定：需要運(yùn)用棧來實(shí)現(xiàn)對(duì)中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，并且再次輸入后綴表達(dá)式，得出結(jié)果。輸入形式、輸入值的范圍；中綴表達(dá)式的輸入，操作數(shù)必須不為負(fù)數(shù)，并且表達(dá)式以=結(jié)束輸入輸出形式；第一次輸出后綴表達(dá)式，接著輸出后綴表達(dá)式求得的值程序功能；中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，后綴表達(dá)式求值測試數(shù)據(jù)：10(20-10)+10=2、 概要設(shè)計(jì) ADT定義:class arrStackprivate:int mSize; /棧最多存放元素個(gè)數(shù)int top;/棧頂指針T *st;/存棧元素的數(shù)組public:arrStack(int

2、sizee) /創(chuàng)建定長順序棧的實(shí)例mSize = sizee;top = -1;st =new TmSize;arrStack( ) arrStack( ) void clear( ) bool isEmpty( )bool push(const T item)bool pop(T& item) T& gettop() bool input()int trans()bool Caculator() 主程序流程:各程序模塊間的調(diào)用關(guān)系；3、 詳細(xì)設(shè)計(jì)實(shí)現(xiàn)ADT定義的數(shù)據(jù)類型:arrStack(int sizee) /創(chuàng)建定長順序棧的實(shí)例mSize = sizee;top = -

3、1;st =new TmSize; arrStack( ) /清空top = -1;arrStack( ) /銷毀delete st;void clear( ) /清空top = -1;bool isEmpty( ) /若棧已空返回trueif(top=-1)return true;return false;bool push(const T item) /入棧 O(1)/*if (top=(mSize-1)/若上溢T *newst = new T mSize*2 ;/擴(kuò)容到2倍for(int i = 0; i<= top; i+)/復(fù)制newst i = st i ;delete st

4、; /釋放舊空間st = newst; /恢復(fù)stmSize *=2; /改寫mSize*/st +top = item; /插入itemreturn true;bool pop(T& item) /出棧 O(1)if (top=-1)cout<<"空棧不能刪"<<endl;return false;elseitem=st top- ;return true;T& gettop() /取棧頂O(1)if (top=-1)cout<<"空棧不能讀取"<<endl;elsereturn st t

5、op ; bool input() char in; int i=0; cout<<"請您輸入您要轉(zhuǎn)換的前綴表達(dá)式"<<endl; cin>>in; while(in!='=') ai=in; cin>>in; i+; ai='=' i=0; while(ai!='=') cout<<ai; i+; int trans() int i=0,j=0; char ch,e; ch=ai; while(ch!='=') switch(ch) case 

6、9;(': push(ch); break; case '+': case '-': case '/': case '*': while(!isEmpty() && gettop()!='(' && gettop()<=ch) e=gettop(); bj=e; pop(e); j+; push(ch); break; case ')': if (!isEmpty() while(gettop()!='(') e=gettop(); bj

7、=e; pop(e); j+; pop(e); break; default: if (ch>='0'<='9') bj+=ch; ch=a+i; while(!isEmpty() e=gettop(); bj+=e; pop(e); int k=0; cout<<endl<<"您得到的后綴表達(dá)式為："<<endl; for (;k<j;k+) cout<<bk<<' ' return j;bool Caculator() /全局函數(shù)來計(jì)算后綴表達(dá)式

8、 arrStack<int>s(100); int newope,ope1,ope2,e; char c; cout<<endl<<"請您輸入您得到的后綴表達(dá)式(以輸入等號(hào)結(jié)束):"<<endl; while(cin>>c,c!='=') switch(c) case '+': ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1+ope2);break; case '-': ope2=s.gett

9、op();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1-ope2);break; case '*': ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1*ope2);break; case '/': ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1/ope2);break; default: cin.putback(c); cin>>newope; s.push

10、(newope); break; cout<<endl<<"求得的值為："<<endl; e=s.gettop(); cout<<e<<endl; s.pop(e);4、 調(diào)試分析調(diào)試中遇到的問題、如何解決、對(duì)設(shè)計(jì)與實(shí)現(xiàn)的分析討論；調(diào)試過程中出現(xiàn)了中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式轉(zhuǎn)換錯(cuò)誤的問題，原因是操作符號(hào)優(yōu)先級(jí)判斷判斷錯(cuò)。算法時(shí)空分析；O（n）5、 用戶使用說明A. 按照提示輸入中綴表達(dá)式B. 看到屏幕輸出的后綴表達(dá)式C. 將屏幕輸出的后綴表達(dá)式再次按照屏幕提示輸入D. 看到屏幕輸出的后綴表達(dá)式的值6、 測試結(jié)果列出

11、測試用輸入、輸出；7、 源程序列出源程序清單：#include <iostream>#include<string.h>using namespace std;template <class T>class arrStackprivate:int mSize; /棧最多存放元素個(gè)數(shù)int top;/棧頂指針T *st;/存棧元素的數(shù)組public: char a100; char b100;arrStack(int sizee) /創(chuàng)建定長順序棧的實(shí)例mSize = sizee;top = -1;st =new TmSize; arrStack( ) /清空

12、top = -1;arrStack( ) /銷毀delete st;void clear( ) /清空top = -1;bool isEmpty( ) /若棧已空返回trueif(top=-1)return true;return false;bool push(const T item) /入棧 O(1)/*if (top=(mSize-1)/若上溢T *newst = new T mSize*2 ;/擴(kuò)容到2倍for(int i = 0; i<= top; i+)/復(fù)制newst i = st i ;delete st; /釋放舊空間st = newst; /恢復(fù)stmSize *=

13、2; /改寫mSize*/st +top = item; /插入itemreturn true;bool pop(T& item) /出棧 O(1)if (top=-1)cout<<"空棧不能刪"<<endl;return false;elseitem=st top- ;return true;T& gettop() /取棧頂O(1)if (top=-1)cout<<"空棧不能讀取"<<endl;elsereturn st top ; bool input() char in; int i=

14、0; cout<<"請您輸入您要轉(zhuǎn)換的前綴表達(dá)式"<<endl; cin>>in; while(in!='=') ai=in; cin>>in; i+; ai='=' i=0; while(ai!='=') cout<<ai; i+; int trans() int i=0,j=0; char ch,e; ch=ai; while(ch!='=') switch(ch) case '(': push(ch); break; case &

15、#39;+': case '-': case '/': case '*': while(!isEmpty() && gettop()!='(' && gettop()<=ch) e=gettop(); bj=e; pop(e); j+; push(ch); break; case ')': if (!isEmpty() while(gettop()!='(') e=gettop(); bj=e; pop(e); j+; pop(e); break; de

16、fault: if (ch>='0'<='9') bj+=ch; ch=a+i; while(!isEmpty() e=gettop(); bj+=e; pop(e); int k=0; cout<<endl<<"您得到的后綴表達(dá)式為："<<endl; for (;k<j;k+) cout<<bk<<' ' return j;bool Caculator() /全局函數(shù)來計(jì)算后綴表達(dá)式 arrStack<int>s(100); int n

17、ewope,ope1,ope2,e; char c; cout<<endl<<"請您輸入您得到的后綴表達(dá)式(以輸入等號(hào)結(jié)束):"<<endl; while(cin>>c,c!='=') switch(c) case '+': ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1+ope2);break; case '-': ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1-ope2);break; case '*': ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1*ope2);break; case '/': ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e)