后綴表達(dá)式求值

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告評分滿分5分學(xué)號：2015111898 姓名：許明華 專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)知識范疇：棧與隊(duì)列 完成日期：2017年4月03日實(shí)驗(yàn)題目：后綴表達(dá)式求值實(shí)驗(yàn)內(nèi)容及要求：從鍵盤輸入后綴表達(dá)式（運(yùn)算符和操作數(shù)建議以字符串形式輸入，空格作為分隔符），計(jì)算并輸出后綴表達(dá)式的求值結(jié)果。 基本要求：實(shí)現(xiàn) +, -, *, /四個二元運(yùn)算符； 實(shí)現(xiàn)+, -兩個一元運(yùn)算符（即正、負(fù)號）； 操作數(shù)用整數(shù)表示。提高要求：輸出對應(yīng)的前綴表達(dá)式。每位同學(xué)可必須實(shí)現(xiàn)基本要求，可選擇實(shí)現(xiàn)提高要求；程序可不處理表達(dá)式語法錯誤。實(shí)驗(yàn)?zāi)康模赫莆斩褩Ｔ诒磉_(dá)式求值中的應(yīng)用。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)簡要描述：序言：這是本學(xué)期第三個

2、實(shí)驗(yàn)，這個實(shí)驗(yàn)比較的基本要求是要我們求出一個已經(jīng)按后綴表達(dá)式形式輸入的值，除了之前的堆棧部分，新增了一部分就是判斷操作數(shù)和運(yùn)算符，并將操作數(shù)入棧，將運(yùn)算符進(jìn)行對應(yīng)的操作數(shù)功能實(shí)現(xiàn)，并將結(jié)果入棧。數(shù)據(jù)結(jié)構(gòu)簡要設(shè)計(jì)： 本實(shí)驗(yàn)主要可分為兩個大的模塊，一個是堆棧操作，另外一個就是后綴表達(dá)式求值操作。堆棧操作：用結(jié)構(gòu)體類型名來創(chuàng)建用于保存操作數(shù)的堆棧，并實(shí)現(xiàn)判斷?？?、棧滿、棧初始化、入棧以及退棧等操作；后綴表達(dá)式求值操作：用string類型定義一個字符串，并對其進(jìn)行判斷，是操作數(shù)就入棧，是運(yùn)算符就進(jìn)行運(yùn)算，并保存結(jié)果。算法設(shè)計(jì)簡要描述：后綴表達(dá)式求值算法：用string類型定義一個字符串，并用一個swi

3、tch來實(shí)現(xiàn)運(yùn)算符的操作和操作數(shù)的入棧，再用一個while來進(jìn)行循環(huán)遍歷整個字符串，直到字符串的末尾為止。最后將算得最終結(jié)果退棧，并打印到屏幕上即可。輸入/輸出設(shè)計(jì)簡要描述：輸入：從鍵盤上輸入一個已經(jīng)排好序的后綴表達(dá)式，如12-82-74-/*輸出：屏幕上將輸出后綴表達(dá)式的值，如上面表達(dá)式的值為6編程語言說明：1， 編程軟件，Code Blocks 16.0；2， 代碼均用C+語言實(shí)現(xiàn)；3， 輸入輸出采用C+語言的cout和cin函數(shù)；4， 程序注釋采用C/C+規(guī)范；主要函數(shù)說明：void InitStack(Stack *s);/棧的初始化int EmptyStack(Stack *s);/

4、判斷棧空int full(Stack *s);/判斷棧滿int push(Stack *s,elemtype x);/入棧操作int pop(Stack *s,elemtype &x);/退棧操作int result(string s);/后綴表達(dá)式求值程序測試簡要報告：見截圖：1， 2， 源程序代碼：#include<iostream>#include<malloc.h>using namespace std;typedef int elemtype;/整數(shù)型數(shù)據(jù)類型typedef struct elemtype *elem; int length; int

5、top; Stack;/函數(shù)聲明void InitStack(Stack *s);/棧的初始化int EmptyStack(Stack *s);/判斷棧空int full(Stack *s);/判斷棧滿int push(Stack *s,elemtype x);/入棧操作int pop(Stack *s,elemtype &x);/退棧操作int result(string s);/后綴表達(dá)式求值/函數(shù)具體實(shí)現(xiàn)/順序存儲的棧結(jié)構(gòu)，以及其相應(yīng)算法void InitStack(Stack *s) s->length = 100; s->elem = (elemtype *)ma

6、lloc(sizeof(elemtype)*s->length); s->top = -1;/判斷棧是否為空int EmptyStack(Stack *s) return s->top = -1;/判斷棧滿int full(Stack *s) return s->top>=s->length-1;/入棧int push(Stack *s,elemtype x) if(full(s) return 0; s->elem+s->top = x; return 1;/退棧int pop(Stack *s,elemtype &x) if(Empt

7、yStack(s) return 0; x = s->elems->top-; return 1;/后綴表達(dá)式求值函數(shù)int result(string s) int Result;/定義一個保存輸出結(jié)果的值 Stack *p;/建棧 p = (Stack *)malloc(sizeof(Stack);/為新建的棧分配內(nèi)存空間 InitStack(p);/初始化剛建的棧，這一步不進(jìn)行的話，入棧將不能進(jìn)行，之前這個問題將我難到了好久 int i = 0;/定義一個字符串下標(biāo)，用來循環(huán)判斷字符串中的內(nèi)容 elemtype a,b,d;/定義三個elemtype類型變量，用來進(jìn)行操作數(shù)的

8、實(shí)現(xiàn) while(1) if(i>s.length()-1) break; switch(si) case '+':/加號則退兩個，并相加將結(jié)果保存在棧中 pop(p,a); pop(p,b); d = a + b; push(p,d); break; case '-':/加號則退兩個，并相減將結(jié)果保存在棧中 pop(p,a); pop(p,b); d = b - a; push(p,d); break; case '*':/加號則退兩個，并相乘將結(jié)果保存在棧中 pop(p,a); pop(p,b); d = a*b; push(p,d); break; case '/':/加號則退兩個，并相除結(jié)果保存在棧中 pop(p,a); pop(p,b); d = b/a; push(p,d); break; default:/是數(shù)字就轉(zhuǎn)換為數(shù)字后入棧 d = si - '0' push(p,d); break; i+;/字符串自增一進(jìn)行遍歷 pop(p,Result);/將計(jì)算后的結(jié)果退棧 cout<<Result<<endl;/輸出最后的結(jié)果 retu