逆波蘭表達(dá)式求值(實(shí)驗(yàn)報(bào)告及C++源碼).doc

數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)指導(dǎo)書逆波蘭表達(dá)式求值一、需求分析1、從鍵盤中輸入一個(gè)后綴表達(dá)式，該表示包括加減乘除等操作符，以及正整數(shù)作為操作數(shù)等。2、用堆棧來(lái)實(shí)現(xiàn)3、測(cè)試數(shù)據(jù)輸入：2 3 * 1 #輸出：2 3 * 1 - =5二、概要設(shè)計(jì)抽象數(shù)據(jù)類型需要一個(gè)浮點(diǎn)數(shù)棧來(lái)存儲(chǔ)還沒(méi)有計(jì)算的浮點(diǎn)數(shù)或者運(yùn)算的結(jié)果。ADT Stack數(shù)據(jù)成員：int size; int top; /分別用于存儲(chǔ)棧大小、棧頂位置float *listArray;/存儲(chǔ)浮點(diǎn)型數(shù)字的數(shù)組成員函數(shù)：bool push(float it);bool pop(float& it);bool isEmpty(); /判斷棧為空bool isOne();/判斷棧是否只有一個(gè)元素算法的基本思想1. 逐一掃描字符串，用ascii碼進(jìn)行判斷，如果該字符是數(shù)字，則利用x=x*10+stri-48將數(shù)據(jù)由字符類型轉(zhuǎn)換為浮點(diǎn)型數(shù)據(jù)；2. 如果字符是.，則將.轉(zhuǎn)化為小數(shù)點(diǎn)，并將.后的數(shù)據(jù)轉(zhuǎn)化為小數(shù)部分；3. 遇到空格前是數(shù)據(jù)的，將x押入棧；4. 如果該字符是+，-，*或/，判斷棧里的元素是否少于兩個(gè)個(gè)，如果少于兩個(gè)，報(bào)錯(cuò)；如果大于等于兩個(gè)，就彈出兩個(gè)數(shù)據(jù)，并進(jìn)行相應(yīng)的計(jì)算；程序的流程輸入字符串，程序?qū)ψ址来螔呙琛呙枰晃?，處理一位。掃描完成后，判斷棧里是不是只有一個(gè)數(shù)據(jù)，若是，得到正確結(jié)果；若不是，則表達(dá)式出錯(cuò)。三、詳細(xì)設(shè)計(jì)物理數(shù)據(jù)類型用浮點(diǎn)數(shù)類型的棧存儲(chǔ)運(yùn)算中要用的數(shù)據(jù)，需要入棧、出棧，故設(shè)計(jì)如下的浮點(diǎn)類型的棧：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(); /判斷棧里是否只有且僅有一個(gè)元素;成員函數(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語(yǔ)句實(shí)現(xiàn)1. 逐一掃描字符串，用ascii碼進(jìn)行判斷，如果該字符是數(shù)字，則利用x=x*10+stri-48將數(shù)據(jù)由字符類型轉(zhuǎn)換為浮點(diǎn)型數(shù)據(jù)；2. 如果字符是.，則將.轉(zhuǎn)化為小數(shù)點(diǎn)，并將.后的數(shù)據(jù)轉(zhuǎn)化為小數(shù)部分；3. 遇到空格前是數(shù)據(jù)的，將x押入棧；4. 如果該字符是+，-，*或/，判斷棧里的元素是否少于兩個(gè)個(gè)，如果少于兩個(gè)，報(bào)錯(cuò)；如果大于等于兩個(gè)，就彈出兩個(gè)數(shù)據(jù)，并進(jìn)行相應(yīng)的計(jì)算；算法的時(shí)空分析因?yàn)槿霔！⒊鰲５臅r(shí)間復(fù)雜度均為(1)，所以時(shí)間的復(fù)雜度主要取決于字符串的長(zhǎng)度，空間也同樣取決于字符串長(zhǎng)度。時(shí)間復(fù)雜度為(n)。輸入和輸出的格式輸入：2 3 * 1 #輸出：2 3 * 1 - =5五、測(cè)試結(jié)果六、用戶使用說(shuō)明（可選）1. 運(yùn)行程序后，直接輸入后綴表達(dá)式；2. 用戶輸入的表達(dá)式必須符合后綴表達(dá)式的要求，并以#號(hào)結(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();/判斷棧里是否一個(gè)元素;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ù)傳進(jìn)輸入的字符串，并對(duì)字符串進(jìn)/行掃描并進(jìn)行相應(yīng)處理，得到結(jié)果(函數(shù)聲/明)void compute(char* str); int main()char str20;cin.getline(str,20,#);compute(str);return 0;/此函數(shù)傳進(jìn)輸入的字符串，并對(duì)字符串進(jìn)/行掃描并進(jìn)行相應(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 +: /加法運(yùn)算if(aStack.isOne()|aStack.isEmpty() cout 表達(dá)式不符合要求;return;aStack.pop(s1);aStack.pop(s2);x=s2+s1;aStack.push(x);x=0;i+;break;case -: /減法運(yùn)算if(aStack.isOne()|aStack.isEmpty()cout 表達(dá)式不符合要求;return;aStack.pop(s1); aStack.pop(s2);x=s2-s1; aStack.push(x);x=0; i+;break;case *: /乘法運(yùn)算if(aStack.isOne()|aStack.isEmpty()cout 表達(dá)式不符合要求;return;aStack.pop(s1); aStack.pop(s2);x=s2*s1;aStack.push(x);x=0;i+;break;case /: /除法運(yùn)算if(aStack.isOne()|aStack.isEmpty()cout 表達(dá)式不符合要求;return;aStack.pop(s1);a