逆波蘭表達式求值(實驗報告及C++源碼)

1、數(shù)據(jù)結(jié)構(gòu)課程實驗指導書逆波蘭表達式求值一、需求分析1、從鍵盤中輸入一個后綴表達式，該表示包括加減乘除等操作符，以及正整數(shù)作為操 作數(shù)等。2、用堆棧來實現(xiàn)3、測試數(shù)據(jù)輸入：2 3 * 1 -#輸出：2 3 * 1 - =5二、概要設(shè)計抽象數(shù)據(jù)類型需要一個浮點數(shù)棧來存儲還沒有計算的浮點數(shù)或者運算的結(jié)果。ADT Stack數(shù)據(jù)成員：int size; int top; II分別用于存儲棧大小、棧頂位置float *listArray;存儲浮點型數(shù)字的數(shù)組成員函數(shù)：bool push(float it);bool pop(float& it);bool isEmpty(); II 判斷棧為空bool

2、isOne();判斷棧是否只有一個元素算法的基本思想1. 逐一掃描字符串，用ascii碼進行判斷，如果該字符是數(shù)字，則利用x=x*10+stri-48 將數(shù)據(jù)由字符類型轉(zhuǎn)換為浮點型數(shù)據(jù)；2. 如果字符是.則將.轉(zhuǎn)化為小數(shù)點，并將后的數(shù)據(jù)轉(zhuǎn)化為小數(shù)部分；3. 遇到空格前是數(shù)據(jù)的，將x押入棧；4. 如果該字符是或，判斷棧里的元素是否少于兩個個，如果少于兩個， 報錯；如果大于等于兩個，就彈出兩個數(shù)據(jù)，并進行相應(yīng)的計算；程序的流程輸入字符串，程序?qū)ψ址来螔呙?。掃描一位，處理一位。掃描完成后，判斷棧里是不是只有一個數(shù)據(jù)，若是，得到正確結(jié)果；若不是，則表達式出錯。三、詳細設(shè)計物理數(shù)據(jù)類型用浮點數(shù)類型的

3、棧存儲運算中要用的數(shù)據(jù)，需要入棧、出棧，故設(shè)計如下的浮點類型的棧：class Stackprivate:int size;int top;float *listArray;public:Stack(i nt sz=20);Stack();bool push(float it);/ 入棧bool pop(float& it);/ 出棧bool isEmpty();判斷棧是否為空bool isOn e(); /判斷棧里是否只有且僅有一個元素；6成員函數(shù)的函數(shù)體Stack:Stack(i nt sz)棧構(gòu)造函數(shù)size=sz;top=0;listArray=new floatsize;bool St

4、ack:push(float it)if(top=size)return false; listArraytop+=it; return true;bool Stack:pop(float& it)if(top=0)return false;it=listArray-top;return true;bool Stack:isEmpty() / 判斷站是否為空if(top=0)return true;return false;bool Stack:isO ne()if(top=1)return true;return false;Stack:Stack()delete listArray;算法的

5、具體步驟用switch語句實現(xiàn)1. 逐一掃描字符串，用ascii碼進行判斷，如果該字符是數(shù)字，則利用x=x*10+stri-48 將數(shù)據(jù)由字符類型轉(zhuǎn)換為浮點型數(shù)據(jù)；2. 如果字符是.則將.轉(zhuǎn)化為小數(shù)點，并將 后的數(shù)據(jù)轉(zhuǎn)化為小數(shù)部分；3. 遇到空格前是數(shù)據(jù)的，將x押入棧；4. 如果該字符是或，判斷棧里的元素是否少于兩個個，如果少于兩個， 報錯；如果大于等于兩個，就彈出兩個數(shù)據(jù)，并進行相應(yīng)的計算；算法的時空分析因為入棧、出棧的時間復雜度均為(1)，所以時間的復雜度主要取決于字符串的長度，空間也同樣取決于字符串長度。時間復雜度為(n)。輸入和輸出的格式輸入：2 3 * 1 -#輸出：2 3 * 1

6、- =5五、測試結(jié)果- E : Conr se逆海蘭 hli&bugA逆液 二.exe3 * 4 - E * 4 - -2fkunn any hcjy to cont xhag六、用戶使用說明（可選）1. 運行程序后，直接輸入后綴表達式；2. 用戶輸入的表達式必須符合后綴表達式的要求，并以#號結(jié)束。七、附錄（可選）#in elude #in elude using n amespaee std; class Stackprivate:int size;int top;float *listArray;public:Stack(i nt sz=20);Stack();bool push(floa

7、t it);/ 入棧bool pop(float& it);/ 出棧bool isEmpty();判斷棧是否為空bool isO ne();判斷棧里是否一個元素 ;Stack:Stack(i nt sz)/ 棧構(gòu)造函數(shù)size=sz;top=0;listArra y=new floatsize;bool Stack:push(float it)if(top=size)return false;listArraytop+=it;return true;bool Stack:pop(float& it)if(top=0)return false;it=listArray-top;return tr

8、ue;bool Stack:isEmpty() / 判斷站是否為空if(top=0)return true;return false;bool Stack:isO ne()if(top=1)return true;return false;Stack:Stack()delete listArray;/此函數(shù)傳進輸入的字符串，并對字符串進/行掃描并進行相應(yīng)處理，得到結(jié)果(函數(shù)聲/明)void compute(char* str);int mai n()char str20;cin. getli ne(str,20,#); compute(str);return 0;/此函數(shù)傳進輸入的字符串，并對

9、字符串進/行掃描并進行相應(yīng)處理，得到結(jié)果(函數(shù)體)void compute(char* str)Stack aStack;float x=0,y=0,s1,s2,temp;int i;i=0;while(stri)switch(stri)case +: 加法運算if(aStack.isO ne()|aStack.isEmpty() cout 表達式不符合要求; return; aStack.pop(s1); aStack.pop(s2);x=s2+s1;aStack.push(x); x=0;i+;break;case -: 減法運算if(aStack.isO ne()|aStack.isEm

10、pty() cout 表達式不符合要求; return;aStack.pop(s1); aStack.pop(s2); x=s2-s1;aStack.push(x);x=0;i+;break;case *: /乘法運算if(aStack.isO ne()|aStack.isEmpty() cout 表達式不符合要求; return;aStack.pop(s1); aStack.pop(s2); x=s2*s1;aStack.push(x);x=0;i+;break;case /: /除法運算if(aStack.isO ne()|aStack.isEmpty()cout 表達式不符合要求;return;aStack.pop(sl);a