完整版數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-表達(dá)式求值問題

1、實(shí)驗(yàn) 表達(dá)式求值問題1.問題描述表達(dá)式是數(shù)據(jù)運(yùn)算的根本形式.人們的書寫習(xí)慣是中綴式,如： 11+22* (7-4) /3.中綴 式的計(jì)算按運(yùn)算符的優(yōu)先級(jí)及括號(hào)優(yōu)先的原那么,相同級(jí)別從左到右進(jìn)行計(jì)算.表達(dá)式還有后綴表達(dá)式(如：11 22 7 4 - * 3 / +)和前綴表達(dá)式(+ 11 / * 22 - 7 4 3).后綴表達(dá)式和前綴表達(dá)式中沒有括號(hào),給計(jì)算帶來方便.如后綴表達(dá)式計(jì)算時(shí)按運(yùn)算符出現(xiàn)的先后進(jìn)行計(jì)算.本設(shè)計(jì)的主要任務(wù)是進(jìn)行表達(dá)式形式的轉(zhuǎn)換及不同形式的表達(dá)式計(jì)算.2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)(1)順序棧類定義：首先應(yīng)在類中定義成員函數(shù),以此來完成順序棧的相關(guān)操作,如下:class SqStack

2、(private:T *base;int top;int stacksize;public:SqStack(int m);/SqStack()delete 口 base;top=0;stacksize=0;void Push(T x);T Pop();T GetTop();int StackEmpty();void ClearStack();void StackTop();void StackTranverse();/棧底指針棧頂棧容量構(gòu)建函數(shù)析構(gòu)函數(shù)入棧出棧獲取棧頂元素/ 測(cè)?？?清空棧/返回棧頂指針/顯示棧中元素;(2)順序棧類實(shí)現(xiàn)：對(duì)順序棧進(jìn)行初始化,初始化的首要操作就是創(chuàng)立一個(gè)空順序棧

3、.Step1 :申請(qǐng)一組連續(xù)的內(nèi)存空間為順序棧使用：base=new Tm;i f(base=NULL)cout<<"棧創(chuàng)立失敗,退出!"<<endl;exit(1);)Step2 ：給棧頂、棧容量賦相應(yīng)的值：stacksize=m;t op=-1;(2)順序棧入棧：入棧需要在棧頂插入一個(gè)新元素并相應(yīng)的調(diào)整棧頂.Step1 :首先判斷是否棧滿,如果棧滿,拋出“上溢信息,無法入棧,否那么轉(zhuǎn)入Step2;if(top=stacksize-1) throw " 棧滿,無法入棧"Step2 :棧頂指針增加1;top+;Step3 :新元素

4、插入棧頂位置；basetop=x;(3)順序棧出棧：出棧需要取出棧頂元素,并相應(yīng)的調(diào)整棧頂指針.Step1 :首先判斷是否?？?如果?？?拋出“下溢信息,無法出棧,否那么轉(zhuǎn)入Step2;i f(top=-1) throw " ?？?不能出棧"Step2：取出棧頂元素,棧頂指針減1;T x;x=basetop-;Step3 :返回棧頂元素；return x ;(4)順序棧取棧頂元素：取棧頂元素是取出棧頂元素的值,但不改變棧.Step1 :首先判斷是否?？?如果?？?拋出“下溢信息,無法出棧,否那么轉(zhuǎn)入Step2;if(top=-1) throw " ?？?棧頂無元素

5、 "Step2：取出棧頂元素,返回棧頂元素；return basetop;(5)判斷?？眨号袛嗍欠駰？?返回Step1 :如果?？?返回 1,否那么轉(zhuǎn)Step2 ;if(top=-1)return 1;Step2 ：否那么返回0;return 0;(6)清空棧：將棧清空.top=-1(7)返回棧頂指針：cout<<"棧頂 top= "<<top;(8)輸出棧元素：將棧頂指向i ,從棧頂輸出到棧底.Stepl :將棧頂指針賦予i ;int i=top;Step2 ：如果棧不為空,那么輸出；while(i>=0)cout<<b

6、asei-<<'t'cout<<endl;3.算法設(shè)計(jì)本實(shí)驗(yàn)要求讀入中綴表達(dá)式,求中綴表達(dá)式,將中綴表達(dá)式轉(zhuǎn)換成前,后綴表達(dá)式,利用前,中,后綴表達(dá)式求值,并且能夠輸出等等操作,這就需要構(gòu)建相關(guān)算法.(1)首先要將表達(dá)式中操作符優(yōu)先級(jí)進(jìn)行排序,優(yōu)先級(jí)從高到低依次為(,),*,/,+,-,算法如下,利用選擇語句比較：char Precede(char t1,char t2)/運(yùn)算符的優(yōu)先級(jí)比較char f;switch(t2)case '+':case '-':if(t1='('|t1='='

7、) f='<'elsef='>'break;casecase '/':if(t1='*'11t1='/'|t1=')') f='>'elsef='<'break;case '(':if(t1=')')cout<<"ERROR1"<<endl;exit(0);elsef='<'break;case ')':switch(t1)(cas

8、e '(':f='='break;case '=':cout<<"ERROR2"<<endl;exit(0);default: f='>'break;case '=':switch(t1)(case '=':f='='break;case '(':cout<<"ERROR2"<<endl;exit(0);default: f='>'return f;(2

9、)其次,就是判斷輸入元素是否為運(yùn)算符,假設(shè)為運(yùn)算符,就輸出 1,否那么輸出0;int In(char c) / 判斷c是否為運(yùn)算符switch(c)case'+':case'-':case'*':case'/':case'(':case')':case'=':return 1;default:return 0;)(3)構(gòu)造表達(dá)式的運(yùn)算算法,利用選擇語句將運(yùn)算分類：float Operate(float a,char theta,float b)/實(shí)施一次運(yùn)算float c;switc

10、h(theta)case'+':c=a+b;break;case'-':c=a-b;break;case'*':c=a*b;break;case'/':c=a/b;)return c;)(4)要求一：中綴表達(dá)式求值Step1 :首先需要將運(yùn)算符和運(yùn)算數(shù)分開存放,這就需要分別創(chuàng)立棧：SqStack<char> OP(20);SqStack<float> OD(20);Step2:創(chuàng)立相關(guān)字符來存放由鍵盤輸入的字符,并以“=鍵結(jié)束char theta;float a,b,d;char c,x; /存放由鍵盤接收

11、的字符char z6; /存放符點(diǎn)數(shù)字符串int i;OP.Push('=');Step3:當(dāng)輸入為數(shù)字元素是,直接存入表達(dá)式棧就可以,而當(dāng)輸入是符號(hào)元素時(shí),就 需要判斷優(yōu)先級(jí)并進(jìn)行存棧出棧操作,如果是非法字符,輸出錯(cuò)誤,并且不存入；c=*exp+;x=OP.GetTop();while(c!='='|x!='=')if(In(c) /是7種運(yùn)算符之一switch(Precede(x,c)(case'<':OP.Push(c); /c=*exp+;break;case'=':x=OP.Pop(); /c=*e

12、xp+;break;case'>':theta=OP.Pop(); b=OD.Pop();a=OD.Pop();OD.Push(Operate(a,theta,b)else if(c>='0'&&c<='9'|c='.') c(i=0;do(zi=c;i+;c=*exp+;while(c>='0'&&c<='9'|c='.');zi='0'd=atof(z); /將字符串?dāng)?shù)純棧頂元素優(yōu)先權(quán)低脫括號(hào)并接收下一

13、字符退棧并將運(yùn)算結(jié)果入棧是操作數(shù)OD.Push(d);else / c是非法字符(cout<<"ERROR3"<<endl;exit(0);x=OP.GetTop();d=OD.GetTop();return d;)(4)中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式：Stepl:創(chuàng)立一個(gè)操作符棧；char c,x;int i=0;SqStack<char> OP(20);Step2：從左到右掃描讀取表達(dá)式,執(zhí)行以下運(yùn)算,直至表達(dá)式結(jié)束符.SqStack<char> OP(20);OPPush('='); / =是表達(dá)式結(jié)束標(biāo)志c

14、out<<"exp:"<<exp<<endl;c=*exp+;2.1 ：如果是操作數(shù),輸出；if(c>='0'&&c<='9')|c='.')postexpi+=c;c=*exp+;)2.2 :如果是操作符 A2,把操作符棧棧頂?shù)牟僮鞣鸄2與它比較：2.2.1: : A1<A2, A2如操作符棧.2.2.2: A1=A2,從操作符棧退出一個(gè)操作符,不輸出.2.2.3: A1>A2,從操作符棧輸出所有比A2優(yōu)先級(jí)高的運(yùn)算符,直至棧頂算符優(yōu)先級(jí)小于A2,

15、A2如操作符棧.if(In(c) 是7種運(yùn)算符之一postexpi+=''x=OPGetTop();switch(Precede(x,c)case'<':OP.Push(c); /棧頂元素優(yōu)先權(quán)低c=*exp+;break;case'=':x=OPPop(); 脫括號(hào)并接收下一字符c=*exp+;break;case'>':postexpi+=OP.Pop(); 運(yùn)算符出棧輸出 break;) ) postexpi='0'(4)中綴表達(dá)式轉(zhuǎn)換成前綴表達(dá)式：Step1:創(chuàng)立一個(gè)操作符棧；char c,x;

16、int i=0;SqStack<char> OP(20);Step2：從右到左掃描讀取表達(dá)式,執(zhí)行以下運(yùn)算,直至表達(dá)式結(jié)束符； while(*exp != '0')*exp+;OP.Push('='); / =是表達(dá)式結(jié)束標(biāo)志 c=*exp-;2.1 ：如果是操作數(shù),輸出；if(c>='0'&&c<='9')|c='.')preexpi+=c; c=*exp-;)2.2 :如果是操作符 A2,把操作符棧棧頂?shù)牟僮鞣鸄2與它比較：2.2.1: : A1<A2, A2如操作

17、符棧.2.2.2: A1=A2,從操作符棧退出一個(gè)操作符,不輸出.2.2.3: A1>A2,從操作符棧輸出所有比A2優(yōu)先級(jí)高的運(yùn)算符,直至棧頂算符優(yōu)先級(jí)小于A2, A2如操作符棧.if(In(c) /是7種運(yùn)算符之一 preexpi+=''x=OPGetTop();switch(Precede(x,c) case'<':OPPush(c); 棧頂元素優(yōu)先權(quán)低c=*exp-;break;case'=':x=OPPop(); 脫括號(hào)并接收下一字符c=*exp-;break;case'>':preexpi+=OP.Po

18、p(); 運(yùn)算符出棧輸出break;)preexpi='0'/while(5)后綴表達(dá)式求值：Step1:創(chuàng)立一個(gè)棧,作為操作數(shù)棧；SqStack<float> OD(20);Step2：執(zhí)行以下操作,直到表達(dá)式結(jié)束；2.1 ：讀取表達(dá)式：c=*postexp+;2.2 ：如果是操作數(shù),入操作數(shù)棧；if(c>='0'&&c<='9')|c='.')為操作數(shù)i=0; do zi+=c;c=*postexp+;while(c>='0'&&c<='

19、;9'|c='.');zi='0'd=atof(z);/將字符串?dāng)?shù)組轉(zhuǎn)為符點(diǎn)型存于dOD.Push(d);2.3 如果是操作符 A,從操作數(shù)棧推出兩個(gè)操作數(shù)a, b,進(jìn)行運(yùn)算.并把運(yùn)算結(jié)果入操作數(shù)棧；if(In(c)/c為運(yùn)算符b=OD.Pop (); a=OD.Pop ();OD.Push (Operate(a,c,b);c=*postexp+;) c=*postexp+;)Step3:棧頂元素即為表達(dá)式的值,返回它；v=OD.Pop ();return v;(6)前綴表達(dá)式求值；Step1:創(chuàng)立一個(gè)棧,作為操作數(shù)棧；SqStack<float&

20、gt; OD(20);Step2：執(zhí)行以下操作,直到表達(dá)式結(jié)束；2.1 ：讀取表達(dá)式：c=*preexp-;2.2 ：如果是操作數(shù),入操作數(shù)棧；if(c>='0'&&c<='9')|c='.')為操作數(shù)i=0; do zi+=c;c=*preexp-;while(c>='0'&&c<='9'|c='.');zi='0'd=atof(z);/將字符串?dāng)?shù)組轉(zhuǎn)為符點(diǎn)型存于dOD.Push(d);2.3 如果是操作符 A,從操作數(shù)棧推出

21、兩個(gè)操作數(shù)a, b,進(jìn)行運(yùn)算.并把運(yùn)算結(jié)果入操作數(shù)棧；if(In(c)/c為運(yùn)算符b=OD.Pop ();a=OD.Pop ();OD.Push (Operate(a,c,b);)c=*preexp-;)Step3:棧頂元素即為表達(dá)式的值,返回它;v=OD.Pop ();return v;(7)界面設(shè)計(jì):界面要求簡(jiǎn)潔明了,能夠方便用戶進(jìn)行功能選擇,菜單界面如下:1-創(chuàng)立表達(dá)式2-表達(dá)式求值3-求后綴表達(dá)式4-后綴表達(dá)式求值5-求前綴表達(dá)式6-前綴表達(dá)式求值7-顯示表達(dá)式8-退出4.運(yùn)行與測(cè)試(1)運(yùn)行程序,顯示菜單,如下列圖:'3 'D;VC8MyProjectsE創(chuàng)立表達(dá)式

22、2-表達(dá)式求值3-求后輟表達(dá)式 后綴表達(dá)式求值 5 求前綴表達(dá)式 7前線表達(dá)式求值 ?-顯示表達(dá)式 退出Enter choice：(2)創(chuàng)立表達(dá)式,由中前后綴表達(dá)式計(jì)算結(jié)果如以下列圖所示:Enter choice：1Enter choieoj2 1+2«(7)/3 = 3請(qǐng)輔人表達(dá)式.以=結(jié)束1+2我(14)/3 二請(qǐng)按任意鍵繼續(xù)Enter uhoiumE請(qǐng)按任意誕繼續(xù)(3)將中綴表達(dá)式轉(zhuǎn)化為前后綴表達(dá)式:Enter choice ：3exp：1+2«(7-4)/3=后莖表達(dá)式為：1 2 7 4 * * 3 / +Enter choieo：5expr1+2«(7-

23、4)/3=前綴表達(dá)式為：+ 1 / « 2 - F 4 3請(qǐng)按任芭鍵繼續(xù).二5,調(diào)試記錄及收獲本次試驗(yàn)為表達(dá)式求值實(shí)驗(yàn),首先需要對(duì)表達(dá)式進(jìn)行輸入存入處理,這就需要利用棧的特性,中綴表達(dá)式和中轉(zhuǎn)后都比較容易寫出,就是中轉(zhuǎn)前需要將表達(dá)式從后往前遍歷,這就需要將指針先移到字符串的尾端,我這里運(yùn)用了 while(*exp != '0')*exp+;的代碼,將exp移到最后,從右往左對(duì)c賦值,然后進(jìn)行比較.此時(shí) 得到的前綴表達(dá)式就是347 -2 * / 1 +,此時(shí)利用棧的特性,后進(jìn)先出,將棧頂元素先行壓出,這就反轉(zhuǎn)成了前綴表達(dá)式+ 1 / * 2 - 743 ,此時(shí)就大功告成

24、了.本次試驗(yàn)中,實(shí)現(xiàn)了表達(dá)式的求值和中綴表達(dá)式轉(zhuǎn)換成前后綴表達(dá)式,更重要的是,我理解了棧的使用方法以及指針的運(yùn)用方式.附錄：程序清單：頭文件：/順序棧類定義template <class T>class SqStack(private:T *base;/棧底指針int top;/ 棧頂int stacksize;/ 棧容量public:SqStack(int m);/ 構(gòu)建函數(shù)SqStack()delete base;top=0;stacksize=0;/ 析構(gòu)函數(shù)void Push(T x);/ 入棧T Pop();/出棧T GetTop();/獲取棧頂元素int StackEm

25、pty();/ 測(cè)?？誺oid ClearStack();/ 清空棧void StackTop();/返回棧頂指針void StackTranverse();/顯示棧中元素;/順序棧類實(shí)現(xiàn)template <class T>SqStack<T>二SqStack(int m) (base=new Tm; if(base=NULL) (cout<<"棧創(chuàng)立失敗,退出！"<<endl;exit(1);stacksize=m;top=-1;template <class T>void SqStack<T>二Pu

26、sh(T x) (if(top=stacksize-1) throw "棧滿,無法入棧" top+;basetop=x;cout<<"top : "<<top<<endl; template <class T>T SqStack<T>:Pop()(T x;if(top=-1) throw "?？?不能出棧"x=basetop-;cout<<"top : "<<top<<endl;return x;template <

27、;class T>T SqStack<T>:GetTop()(if(top=-1) throw "棧空,棧頂無元素"/cout<<"top ： "<<top<<endl;return basetop;template <class T>int SqStack<T>:StackEmpty()(if(top=-1)return 1;elsereturn 0;)template <class T>void SqStack<T>:ClearStack()top=

28、-1;)template <class T>void SqStack<T>:StackTop()/返回棧頂指針cout<<"棧頂 top= "<<top;)template <class T>void SqStack<T>:StackTranverse() int i=top;while(i>=0)cout<<basei-<<'t'cout<<endl;)主函數(shù)：#include<iostream.h>/cout,cin#includ

29、e"process.h"/exit()#include"stdio.h"/EOF,NULL#include<string.h>#include<stdlib.h> / atoi()#include"SqStack.h"char pause;char Precede(char t1,char t2)/算符的優(yōu)先級(jí)比較char f;switch(t2)case '+':case '-':if(t1='('|t1='=')f='<'

30、 elsef='>'break;casecase '/':if(t1='*'11t1='/'|t1=')') f='>'elsef='<'break;case '(':if(t1=')')(cout<<"ERROR1"<<endl;exit(0);elsef='<'break;case ')':switch(t1)(case '(':f=

31、'='break;case '=':cout<<"ERROR2"<<endl;exit(0);default: f='>'break;case '=':switch(t1)(case '=':f='='break;case '(':cout<<"ERROR2"<<endl;exit(0);default: f='>'return f; int In(char c) /判

32、斷c是否為運(yùn)算符 switch(c)case'+':case'-':case'*':case'/':case'(':case')':case'=':return 1;default:return 0;)float Operate(float a,char theta,float b)/實(shí)施一次運(yùn)算float c;switch(theta)case'+':c=a+b;break;case'-':c=a-b;break;case'*':c=

33、a*b;break;case'/':c=a/b;)return c;)float Val_Exp(char *exp) /中綴表達(dá)式求值.設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧SqStack<char> OP(20);SqStack<float> OD(20);char theta;float a,b,d;char c,x; /存放由鍵盤接收的字符char z6; /存放符點(diǎn)數(shù)字符串int i;OPPush('='); =是表達(dá)式結(jié)束標(biāo)志c=*exp+;x=OPGetTop();while(c!='='|x!=

34、9;=')if(In(c) 是7種運(yùn)算符之一switch(Precede(x,c)case'<':OPPush(c); 棧頂元素優(yōu)先權(quán)低 c=*exp+;break;case'=':x=OPPop(); 脫括號(hào)并接收下一字符 c=*exp+;break;case'>':theta=OP.Pop(); /退棧并將運(yùn)算結(jié)果入棧 b=OD.Pop();a=OD.Pop();OD.Push(Operate(a,theta,b);else if(c>='0'&&c<='9'|c

35、='.') c是操作數(shù)(i=0;do(zi=c;i+;c=*exp+;while(c>='0'&&c<='9'|c='.');zi='0'd=atof(z);/將字符串?dāng)?shù)組轉(zhuǎn)為符點(diǎn)型存于dOD.Push(d);else / c是非法字符(cout<<"ERROR3"<<endl;exit(0);x=OPGetTop();d=OD.GetTop();return d;void CreatePostExp(char * exp,char * &am

36、p;postexp)/由中綴式求后綴式char c,x;int i=0;SqStack<char> OP(20);OPPush('='); =是表達(dá)式結(jié)束標(biāo)志cout<<"exp:"<<exp<<endl;c=*exp+;while(c)(if(c>='0'&&c<='9')|c='.')(postexpi+=c;c=*exp+;if(In(c) 是7種運(yùn)算符之一(postexpi+=''x=OPGetTop();swi

37、tch(Precede(x,c)(case'<':OPPush(c); 棧頂元素優(yōu)先權(quán)低c=*exp+;break;case'=':x=OPPop(); 脫括號(hào)并接收下一字符c=*exp+;break;case'>':postexpi+=OP.Pop(); / 運(yùn)算符出棧輸出 break;postexpi='0'/whilecout<<"后綴表達(dá)式為："<<postexp<<endl;void CreatePre(char * exp,char * &pr

38、eexp)/由中綴式求前綴式char c,x;int i=0;SqStack<char> OP(20);cout<<"exp:"<<exp<<endl;while(*exp != ''0')*exp+;OPPush('='); =是表達(dá)式結(jié)束標(biāo)志c=*exp-;while(c)if(c>='0'&&c<='9')|c='.')preexpi+=c;c=*exp-;) if(In(c) /是7種運(yùn)算符之一 (pre

39、expi+=''x=OPGetTop(); switch(Precede(x,c) (case'<':OPPush(c); 棧頂元素優(yōu)先權(quán)低 c=*exp-;break;case'=':x=OPPop(); 脫括號(hào)并接收下一字符 c=*exp-;break;case'>':preexpi+=OP.Pop(); / 運(yùn)算符出棧輸出 break;) ) preexpi='0'/whilecout<<"前綴表達(dá)式為："<<preexpi-<<endl;f

40、loat Val_PostExp(char *postexp)/后綴表達(dá)式求值int i;char z6;float v=0,d=0,a,b;char c;SqStack<float> OD(20);c=*postexp+; while(c!=''0') if(c>='0'&&c<='9')|c='.') 為操作數(shù) i=0; do zi+=c;c=*postexp+;while(c>='0'&&c<='9'|c='.

41、');zi='0'd=atof(z); /將字符串?dāng)?shù)組轉(zhuǎn)為符點(diǎn)型存于dOD.Push(d);if(In(c)/c為運(yùn)算符 (b=OD.Pop ();a=OD.Pop ();OD.Push (Operate(a,c,b);c=*postexp+;c=*postexp+;v=OD.Pop ();return v;float Val_PreExp(char *preexp)/前綴表達(dá)式求值int i;char z6;float v=0,d=0,a,b;char c;SqStack<float> OD(20);c=*preexp-;while(c!='

42、9;0')if(c>='0'&&c<='9')|c='.') 為操作數(shù)i=0;dozi+=c;c=*preexp-;while(c>='0'&&c<='9'|c='.');zi='0'd=atof(z); /將字符串?dāng)?shù)組轉(zhuǎn)為符點(diǎn)型存于 OD.Push(d);if(In(c)/c為運(yùn)算符b=OD.Pop ();a=OD.Pop ();OD.Push (Operate(a,c,b);c=*preexp-;c=*preexp-;v=OD.Pop (); return v;)/主函數(shù)void main()(/int i;char exp20="(2.2+5)+4*(5-3.1)="char *postexp;postexp=new char20;*postexp='0'/char c;float v1;system("cls");執(zhí)行系統(tǒng)命令cls,清