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

2、構 順序棧： int型數字棧 char型字符棧/*-+121 Top=-1 Top=-1 2.2 關鍵算法分析1.判斷輸入字符是否為運算符int IsOpr(char c) /判斷輸入字符是否為運算符 if (c='+'|c='-'|c='*'|c='/'|c='('|c=')'|c='#') return 1; else return 0; 2. 判斷字符的優先級將判斷條件分為多種情況:如果棧頂元素是+、-的情況與剛取得的字符大小比較如果是+、-則返回>，如果是*、/則返回&

3、lt;，如果是左括號則返回<，如果是右括號則返回>，其他情況則返回>如果棧頂元素是*、/的情況與剛取得的字符大小比較如果是+、-則返回>，如果是*、/則返回>，如果是左括號則返回<，如果是右括號則返回>，其他情況則返回>如果棧頂元素是（的情況與剛取得的字符大小比較，除了右括號是=以外，其他都是返回<如果棧頂元素是)的情況與剛取得的字符大小比較，都是返回>如果棧頂元素是#的情況與剛取得的字符大小比較，除了#返回=以外，其他都是返回>這個方法即將中序表達式轉換為后綴表達式char Precede(char s,char c) /判斷

4、字符的優先級 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.計算int Operate(int x,char opr,int y) /計算 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. 程序運行結果程序運行圖開始 定義數字棧S1符號棧S2輸入字符串S讀取字符SjSj!=0 N YSj是計算符號？ NS1.push(sj) Y與棧頂符號比較優先級結束循環J+輸出S1.POP><Theta=S2.pop ( )=S2.pop ( )S2.push(sj)結束a=S1.pop ( )J+J+b=S

8、1.pop ( )計算（a，theta，b）S1.push(結果)源代碼:#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(); /進棧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); /判斷輸入字符是否為運算符 char Precede(char s,char c); /判斷字符的優先級 int Operate(int x,char opr,int y); /計算 int IsOpr(char c) /判斷輸入字符是否為運算符 if (c='+'|c='-'|c='*'|c='/'|c='('|c=')'|c='#

11、9;) return 1; else return 0; char Precede(char s,char c) /判斷字符的優先級 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) /計算 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;/運算數棧Stack<char> s2;/運算符棧s2.Push('#');int a,b,result,i,n,j=0; c

15、har theta;string s;cout<<"請輸入算式,出入#號結束"<<endl;cin>>s;while(sj!='0')if(!IsOpr(sj) /是運算數的情況 i=sj-'0'/將字符型轉為整型j+; while(!IsOpr(sj) /使得可以輸入幾位數 n=sj-'0'i=i*10+n;j+; s1.Push(i); else switch(Precede(s2.GetTop(),sj) /比較棧頂運算符和剛輸入運算符的優先級 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. 總結這次的實驗選了題目四，用棧做計算器，在寫之前一直覺得這是一個很簡單的實驗，主要是在網上看到棧做計算器的想，所以覺得應該沒什么難度，但是真正做起來才發現難上加難。尤其是在做中綴轉成后綴的時候，其實這個本來有個想法是用樹來做，中綴表達式是樹的中序遍歷（當然要注意運算符的優先級），而后綴表達式是樹的后序遍歷，最初的想法是將中綴表達式轉化成為樹，然后對樹做后序遍歷就能得到后綴表達式，但是此次實驗是以棧、隊