實(shí)驗(yàn)4棧的應(yīng)用

1、北京郵電大學(xué)信息與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 實(shí)驗(yàn)4棧的應(yīng)用學(xué)生姓名： 班 級(jí)： 班內(nèi)序號(hào)： 15學(xué) 號(hào)： 日 期： 2015年12月28日1 實(shí)驗(yàn)要求表達(dá)式求值是程序設(shè)計(jì)語言編譯中最近本的問題，它要求把一個(gè)表達(dá)式翻譯成能夠直接求值的序列。例如用戶輸入字符串“14+(13-2)*2-11*5)*2”，程序可以自動(dòng)計(jì)算得到最終的結(jié)果。在這里，我們將問題簡化，假定算數(shù)表達(dá)式的值均為非負(fù)整數(shù)常數(shù)，不包含變量、小數(shù)和字符常量。試設(shè)計(jì)一個(gè)算術(shù)四則運(yùn)算表達(dá)式求值的簡單計(jì)算器?；疽螅?、 操作數(shù)均為非負(fù)整數(shù)常數(shù)，操作符僅為+、-、*、/、（和）；2、 編寫main函數(shù)進(jìn)行測試。2.1 存儲(chǔ)結(jié)

2、構(gòu) 順序棧： int型數(shù)字棧 char型字符棧/*-+121 Top=-1 Top=-1 2.2 關(guān)鍵算法分析1.判斷輸入字符是否為運(yùn)算符int IsOpr(char c) /判斷輸入字符是否為運(yùn)算符 if (c='+'|c='-'|c='*'|c='/'|c='('|c=')'|c='#') return 1; else return 0; 2. 判斷字符的優(yōu)先級(jí)將判斷條件分為多種情況:如果棧頂元素是+、-的情況與剛?cè)〉玫淖址笮”容^如果是+、-則返回>，如果是*、/則返回&

3、lt;，如果是左括號(hào)則返回<，如果是右括號(hào)則返回>，其他情況則返回>如果棧頂元素是*、/的情況與剛?cè)〉玫淖址笮”容^如果是+、-則返回>，如果是*、/則返回>，如果是左括號(hào)則返回<，如果是右括號(hào)則返回>，其他情況則返回>如果棧頂元素是（的情況與剛?cè)〉玫淖址笮”容^，除了右括號(hào)是=以外，其他都是返回<如果棧頂元素是)的情況與剛?cè)〉玫淖址笮”容^，都是返回>如果棧頂元素是#的情況與剛?cè)〉玫淖址笮”容^，除了#返回=以外，其他都是返回>這個(gè)方法即將中序表達(dá)式轉(zhuǎn)換為后綴表達(dá)式char Precede(char s,char c) /判斷

4、字符的優(yōu)先級(jí) switch(s) case '+': case '-': if(c='+'|c='-') return '>' else if (c='*'|c='/') return '<' else if(c='(') return '<' else if(c=')') return '>' else return '>' break; case '

5、;*': case '/': if(c='+'|c='-') return '>' else if (c='*'|c='/') return '>' else if(c='(') return '<' else if(c=')') return '>' else return '>' break; case '(': if(c=')')

6、 return '=' else return '<' break; case ')': return '>' break; case '#': if(c='#') return '=' else return '<' break; 3.計(jì)算int Operate(int x,char opr,int y) /計(jì)算 int result; switch (opr) case '+': result = x + y; break; ca

7、se '-': result = x - y; break; case '*': result = x * y; break; case '/': result = x / y; break; return result; 3. 程序運(yùn)行結(jié)果程序運(yùn)行圖開始 定義數(shù)字棧S1符號(hào)棧S2輸入字符串S讀取字符SjSj!=0 N YSj是計(jì)算符號(hào)？ NS1.push(sj) Y與棧頂符號(hào)比較優(yōu)先級(jí)結(jié)束循環(huán)J+輸出S1.POP><Theta=S2.pop ( )=S2.pop ( )S2.push(sj)結(jié)束a=S1.pop ( )J+J+b=S

8、1.pop ( )計(jì)算（a，theta，b）S1.push(結(jié)果)源代碼:#include<iostream>#include<string>using namespace std;const int Max=128;template<class T>class Stackpublic:Stack()top=-1;void Push(T x); /入棧T Pop(); /進(jìn)棧T GetTop(); /取棧頂元素int isEmpty(); /判斷棧是否為空private:int top;T dataMax;template<class T>voi

9、d Stack<T>:Push(T x)if(top>=Max-1) throw "上溢"top +;datatop=x;template<class T>T Stack<T>:Pop()if(isEmpty() throw "下溢"top-;return datatop+1;template<class T>T Stack<T>:GetTop()if(isEmpty()throw "下溢"return datatop;template<class T>in

10、t Stack<T>:isEmpty()if(top=-1)return 1;elsereturn 0;int IsOpr(char c); /判斷輸入字符是否為運(yùn)算符 char Precede(char s,char c); /判斷字符的優(yōu)先級(jí) int Operate(int x,char opr,int y); /計(jì)算 int IsOpr(char c) /判斷輸入字符是否為運(yùn)算符 if (c='+'|c='-'|c='*'|c='/'|c='('|c=')'|c='#

11、9;) return 1; else return 0; char Precede(char s,char c) /判斷字符的優(yōu)先級(jí) switch(s) case '+': case '-': if(c='+'|c='-') return '>' else if (c='*'|c='/') return '<' else if(c='(') return '<' else if(c=')') retur

12、n '>' else return '>' break; case '*': case '/': if(c='+'|c='-') return '>' else if (c='*'|c='/') return '>' else if(c='(') return '<' else if(c=')') return '>' else retu

13、rn '>' break; case '(': if(c=')') return '=' else return '<' break; case ')': return '>' break; case '#': if(c='#') return '=' else return '<' break; int Operate(int x,char opr,int y) /計(jì)算 int result;

14、switch (opr) case '+': result = x + y; break; case '-': result = x - y; break; case '*': result = x * y; break; case '/': result = x / y; break; return result; void main()Stack<int> s1;/運(yùn)算數(shù)棧Stack<char> s2;/運(yùn)算符棧s2.Push('#');int a,b,result,i,n,j=0; c

15、har theta;string s;cout<<"請輸入算式,出入#號(hào)結(jié)束"<<endl;cin>>s;while(sj!='0')if(!IsOpr(sj) /是運(yùn)算數(shù)的情況 i=sj-'0'/將字符型轉(zhuǎn)為整型j+; while(!IsOpr(sj) /使得可以輸入幾位數(shù) n=sj-'0'i=i*10+n;j+; s1.Push(i); else switch(Precede(s2.GetTop(),sj) /比較棧頂運(yùn)算符和剛輸入運(yùn)算符的優(yōu)先級(jí) case '<':

16、 s2.Push(sj); j+; break; case '=': theta=s2.Pop(); j+;break; case '>': theta=s2.Pop(); b=s1.Pop(); a=s1.Pop(); result=Operate(a,theta,b); s1.Push(result); break; cout<<s1.GetTop()<<endl;4. 總結(jié)這次的實(shí)驗(yàn)選了題目四，用棧做計(jì)算器，在寫之前一直覺得這是一個(gè)很簡單的實(shí)驗(yàn)，主要是在網(wǎng)上看到棧做計(jì)算器的想，所以覺得應(yīng)該沒什么難度，但是真正做起來才發(fā)現(xiàn)難上加難。尤其是在做中綴轉(zhuǎn)成后綴的時(shí)候，其實(shí)這個(gè)本來有個(gè)想法是用樹來做，中綴表達(dá)式是樹的中序遍歷（當(dāng)然要注意運(yùn)算符的優(yōu)先級(jí)），而后綴表達(dá)式是樹的后序遍歷，最初的想法是將中綴表達(dá)式轉(zhuǎn)化成為樹，然后對樹做后序遍歷就能得到后綴表達(dá)式，但是此次實(shí)驗(yàn)是以棧、隊(duì)