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

1、實驗 表達式求值問題1.問題描述表達式是數(shù)據(jù)運算的根本形式.人們的書寫習(xí)慣是中綴式,如： 11+22* (7-4) /3.中綴 式的計算按運算符的優(yōu)先級及括號優(yōu)先的原那么,相同級別從左到右進行計算.表達式還有后綴表達式(如：11 22 7 4 - * 3 / +)和前綴表達式(+ 11 / * 22 - 7 4 3).后綴表達式和前綴表達式中沒有括號,給計算帶來方便.如后綴表達式計算時按運算符出現(xiàn)的先后進行計算.本設(shè)計的主要任務(wù)是進行表達式形式的轉(zhuǎn)換及不同形式的表達式計算.2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(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ù)入棧出棧獲取棧頂元素/ 測?？?清空棧/返回棧頂指針/顯示棧中元素;(2)順序棧類實現(xiàn)：對順序棧進行初始化,初始化的首要操作就是創(chuàng)立一個空順序棧

3、.Step1 :申請一組連續(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)順序棧入棧：入棧需要在棧頂插入一個新元素并相應(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è)計本實驗要求讀入中綴表達式,求中綴表達式,將中綴表達式轉(zhuǎn)換成前,后綴表達式,利用前,中,后綴表達式求值,并且能夠輸出等等操作,這就需要構(gòu)建相關(guān)算法.(1)首先要將表達式中操作符優(yōu)先級進行排序,優(yōu)先級從高到低依次為(,),*,/,+,-,算法如下,利用選擇語句比較：char Precede(char t1,char t2)/運算符的優(yōu)先級比較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、)其次,就是判斷輸入元素是否為運算符,假設(shè)為運算符,就輸出 1,否那么輸出0;int In(char c) / 判斷c是否為運算符switch(c)case'+':case'-':case'*':case'/':case'(':case')':case'=':return 1;default:return 0;)(3)構(gòu)造表達式的運算算法,利用選擇語句將運算分類：float Operate(float a,char theta,float b)/實施一次運算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)要求一：中綴表達式求值Step1 :首先需要將運算符和運算數(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; /存放符點數(shù)字符串int i;OP.Push('=');Step3:當(dāng)輸入為數(shù)字元素是,直接存入表達式棧就可以,而當(dāng)輸入是符號元素時,就 需要判斷優(yōu)先級并進行存棧出棧操作,如果是非法字符,輸出錯誤,并且不存入；c=*exp+;x=OP.GetTop();while(c!='='|x!='=')if(In(c) /是7種運算符之一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)低脫括號并接收下一

13、字符退棧并將運算結(jié)果入棧是操作數(shù)OD.Push(d);else / c是非法字符(cout<<"ERROR3"<<endl;exit(0);x=OP.GetTop();d=OD.GetTop();return d;)(4)中綴表達式轉(zhuǎn)換成后綴表達式：Stepl:創(chuàng)立一個操作符棧；char c,x;int i=0;SqStack<char> OP(20);Step2：從左到右掃描讀取表達式,執(zhí)行以下運算,直至表達式結(jié)束符.SqStack<char> OP(20);OPPush('='); / =是表達式結(jié)束標志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,從操作符棧退出一個操作符,不輸出.2.2.3: A1>A2,從操作符棧輸出所有比A2優(yōu)先級高的運算符,直至棧頂算符優(yōu)先級小于A2,

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

16、int i=0;SqStack<char> OP(20);Step2：從右到左掃描讀取表達式,執(zhí)行以下運算,直至表達式結(jié)束符； while(*exp != '0')*exp+;OP.Push('='); / =是表達式結(jié)束標志 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,從操作符棧退出一個操作符,不輸出.2.2.3: A1>A2,從操作符棧輸出所有比A2優(yōu)先級高的運算符,直至棧頂算符優(yōu)先級小于A2, A2如操作符棧.if(In(c) /是7種運算符之一 preexpi+=''x=OPGetTop();switch(Precede(x,c) case'<':OPPush(c); 棧頂元素優(yōu)先權(quán)低c=*exp-;break;case'=':x=OPPop(); 脫括號并接收下一字符c=*exp-;break;case'>':preexpi+=OP.Po

18、p(); 運算符出棧輸出break;)preexpi='0'/while(5)后綴表達式求值：Step1:創(chuàng)立一個棧,作為操作數(shù)棧；SqStack<float> OD(20);Step2：執(zhí)行以下操作,直到表達式結(jié)束；2.1 ：讀取表達式：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)為符點型存于dOD.Push(d);2.3 如果是操作符 A,從操作數(shù)棧推出兩個操作數(shù)a, b,進行運算.并把運算結(jié)果入操作數(shù)棧；if(In(c)/c為運算符b=OD.Pop (); a=OD.Pop ();OD.Push (Operate(a,c,b);c=*postexp+;) c=*postexp+;)Step3:棧頂元素即為表達式的值,返回它；v=OD.Pop ();return v;(6)前綴表達式求值；Step1:創(chuàng)立一個棧,作為操作數(shù)棧；SqStack<float&

20、gt; OD(20);Step2：執(zhí)行以下操作,直到表達式結(jié)束；2.1 ：讀取表達式：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)為符點型存于dOD.Push(d);2.3 如果是操作符 A,從操作數(shù)棧推出

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

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

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

24、了.本次試驗中,實現(xiàn)了表達式的求值和中綴表達式轉(zhuǎ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();/ 測?？誺oid ClearStack();/ 清空棧void StackTop();/返回棧頂指針void StackTranverse();/顯示棧中元素;/順序棧類實現(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)先級比較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是否為運算符 switch(c)case'+':case'-':case'*':case'/':case'(':case')':case'=':return 1;default:return 0;)float Operate(float a,char theta,float b)/實施一次運算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) /中綴表達式求值.設(shè)OPTR和OPND分別為運算符棧和運算數(shù)棧SqStack<char> OP(20);SqStack<float> OD(20);char theta;float a,b,d;char c,x; /存放由鍵盤接收的字符char z6; /存放符點數(shù)字符串int i;OPPush('='); =是表達式結(jié)束標志c=*exp+;x=OPGetTop();while(c!='='|x!=

34、9;=')if(In(c) 是7種運算符之一switch(Precede(x,c)case'<':OPPush(c); 棧頂元素優(yōu)先權(quán)低 c=*exp+;break;case'=':x=OPPop(); 脫括號并接收下一字符 c=*exp+;break;case'>':theta=OP.Pop(); /退棧并將運算結(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)為符點型存于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('='); =是表達式結(jié)束標志cout<<"exp:"<<exp<<endl;c=*exp+;while(c)(if(c>='0'&&c<='9')|c='.')(postexpi+=c;c=*exp+;if(In(c) 是7種運算符之一(postexpi+=''x=OPGetTop();swi

37、tch(Precede(x,c)(case'<':OPPush(c); 棧頂元素優(yōu)先權(quán)低c=*exp+;break;case'=':x=OPPop(); 脫括號并接收下一字符c=*exp+;break;case'>':postexpi+=OP.Pop(); / 運算符出棧輸出 break;postexpi='0'/whilecout<<"后綴表達式為："<<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('='); =是表達式結(jié)束標志c=*exp-;while(c)if(c>='0'&&c<='9')|c='.')preexpi+=c;c=*exp-;) if(In(c) /是7種運算符之一 (pre

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

40、loat Val_PostExp(char *postexp)/后綴表達式求值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)為符點型存于dOD.Push(d);if(In(c)/c為運算符 (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)/前綴表達式求值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)為符點型存于 OD.Push(d);if(In(c)/c為運算符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,清