數據結構課程實驗指導書逆波蘭表達式求值一、需求分析1、從鍵盤中輸入一個后綴表達式，該表示包括加減乘除等操作符，以及正整數作為操作數等。2、用堆棧來實現3、測試數據輸入：2 3 * 1 #輸出：2 3 * 1 - =5二、概要設計抽象數據類型需要一個浮點數棧來存儲還沒有計算的浮點數或者運算的結果。ADT Stack數據成員：int size; int top; /分別用于存儲棧大小、棧頂位置float *listArray;/存儲浮點型數字的數組成員函數：bool push(float it);bool pop(float& it);bool isEmpty(); /判斷棧為空bool isOne();/判斷棧是否只有一個元素算法的基本思想1. 逐一掃描字符串，用ascii碼進行判斷，如果該字符是數字，則利用x=x*10+stri-48將數據由字符類型轉換為浮點型數據；2. 如果字符是.，則將.轉化為小數點，并將.后的數據轉化為小數部分；3. 遇到空格前是數據的，將x押入棧；4. 如果該字符是+，-，*或/，判斷棧里的元素是否少于兩個個，如果少于兩個，報錯；如果大于等于兩個，就彈出兩個數據，并進行相應的計算；程序的流程輸入字符串，程序對字符串依次掃描。掃描一位，處理一位。掃描完成后，判斷棧里是不是只有一個數據，若是，得到正確結果；若不是，則表達式出錯。三、詳細設計物理數據類型用浮點數類型的棧存儲運算中要用的數據，需要入棧、出棧，故設計如下的浮點類型的棧：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(); /判斷棧里是否只有且僅有一個元素;成員函數的函數體 5 Stack:Stack(int sz) /棧構造函數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語句實現1. 逐一掃描字符串，用ascii碼進行判斷，如果該字符是數字，則利用x=x*10+stri-48將數據由字符類型轉換為浮點型數據；2. 如果字符是.，則將.轉化為小數點，并將.后的數據轉化為小數部分；3. 遇到空格前是數據的，將x押入棧；4. 如果該字符是+，-，*或/，判斷棧里的元素是否少于兩個個，如果少于兩個，報錯；如果大于等于兩個，就彈出兩個數據，并進行相應的計算；算法的時空分析因為入棧、出棧的時間復雜度均為(1)，所以時間的復雜度主要取決于字符串的長度，空間也同樣取決于字符串長度。時間復雜度為(n)。輸入和輸出的格式輸入：2 3 * 1 #輸出：2 3 * 1 - =5五、測試結果六、用戶使用說明（可選）1. 運行程序后，直接輸入后綴表達式；2. 用戶輸入的表達式必須符合后綴表達式的要求，并以#號結束。七、附錄（可選）#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) /棧構造函數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;/此函數傳進輸入的字符串，并對字符串進/行掃描并進行相應處理，得到結果(函數聲/明)void compute(char* str); int main()char str20;cin.getline(str,20,#);compute(str);return 0;/此函數傳進輸入的字符串，并對字符串進/行掃描并進行相應處理，得到結果(函數體)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