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

數(shù)據(jù)結(jié)構(gòu)課程實驗指導書逆波蘭表達式求值一、需求分析1、從鍵盤中輸入一個后綴表達式，該表示包括加減乘除等操作符，以及正整數(shù)作為操作數(shù)等。2、用堆棧來實現(xiàn)3、測試數(shù)據(jù)輸入：2 3 * 1 #輸出：2 3 * 1 - =5二、概要設計抽象數(shù)據(jù)類型需要一個浮點數(shù)棧來存儲還沒有計算的浮點數(shù)或者運算的結(jié)果。ADT Stack數(shù)據(jù)成員：int size; int top; /分別用于存儲棧大小、棧頂位置float *listArray;/存儲浮點型數(shù)字的數(shù)組成員函數(shù)：bool push(float it);bool pop(float& it);bool isEmpty(); /判斷棧為空bool 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ù)，并進行相應的計算；程序的流程輸入字符串，程序?qū)ψ址来螔呙?。掃描一位，處理一位。掃描完成后，判斷棧里是不是只有一個數(shù)據(jù)，若是，得到正確結(jié)果；若不是，則表達式出錯。三、詳細設計物理數(shù)據(jù)類型用浮點數(shù)類型的棧存儲運算中要用的數(shù)據(jù)，需要入棧、出棧，故設計如下的浮點類型的棧：class Stackprivate:int size;int top;float *listArray;public:Stack(int sz=20);Stack();bool push(float it);/入棧bool pop(float& it);/出棧bool isEmpty();/判斷棧是否為空bool isOne(); /判斷棧里是否只有且僅有一個元素;成員函數(shù)的函數(shù)體 5 Stack:Stack(int sz) /棧構(gòu)造函數(shù)size=sz;top=0;listArray=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 true;bool Stack:isEmpty() /判斷站是否為空if(top=0)return true;return false;bool Stack:isOne()if(top=1)return true;return false;Stack:Stack()delete listArray;算法的具體步驟用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ù)，并進行相應的計算；算法的時空分析因為入棧、出棧的時間復雜度均為(1)，所以時間的復雜度主要取決于字符串的長度，空間也同樣取決于字符串長度。時間復雜度為(n)。輸入和輸出的格式輸入：2 3 * 1 #輸出：2 3 * 1 - =5五、測試結(jié)果六、用戶使用說明（可選）1. 運行程序后，直接輸入后綴表達式；2. 用戶輸入的表達式必須符合后綴表達式的要求，并以#號結(jié)束。七、附錄（可選）#include #include using namespace std;class Stackprivate:int size;int top;float *listArray;public:Stack(int sz=20);Stack();bool push(float it);/入棧bool pop(float& it);/出棧bool isEmpty();/判斷棧是否為空bool isOne();/判斷棧里是否一個元素;Stack:Stack(int sz) /棧構(gòu)造函數(shù)size=sz;top=0;listArray=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 true;bool Stack:isEmpty() /判斷站是否為空if(top=0)return true;return false;bool Stack:isOne()if(top=1)return true;return false;Stack:Stack()delete listArray;/此函數(shù)傳進輸入的字符串，并對字符串進/行掃描并進行相應處理，得到結(jié)果(函數(shù)聲/明)void compute(char* str); int main()char str20;cin.getline(str,20,#);compute(str);return 0;/此函數(shù)傳進輸入的字符串，并對字符串進/行掃描并進行相應處理，得到結(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.isOne()|aStack.isEmpty() cout 表達式不符合要求;return;aStack.pop(s1);aStack.pop(s2);x=s2+s1;aStack.push(x);x=0;i+;break;case -: /減法運算if(aStack.isOne()|aStack.isEmpty()cout 表達式不符合要求;return;aStack.pop(s1); aStack.pop(s2);x=s2-s1; aStack.push(x);x=0; i+;break;case *: /乘法運算if(aStack.isOne()|aStack.isEmpty()cout 表達式不符合要求;return;aStack.pop(s1); aStack.pop(s2);x=s2*s1;aStack.push(x);x=0;i+;break;case /: /除法運算if(aStack.isOne()|aStack.isEmpty()cout 表達式不符合要求;return;aStack.pop(s1);a