實(shí)驗(yàn)報(bào)告11.8.數(shù)據(jù)結(jié)構(gòu)

1、數(shù)據(jù)結(jié)構(gòu)（雙語(yǔ)）項(xiàng)目文檔報(bào)告用兩種方式實(shí)現(xiàn)表達(dá)式自動(dòng)計(jì)算專 業(yè)： 網(wǎng)絡(luò)工程 班 級(jí)： 13網(wǎng)絡(luò)1班 指導(dǎo)教師： 吳亞峰 姓 名： 霍國(guó)豪 學(xué) 號(hào)： 2 13 / 15文檔可自由編輯打印目 錄一、設(shè)計(jì)思想.01二、算法流程圖.02三、源代碼.04四、運(yùn)行結(jié)果.12五、遇到的問(wèn)題及解決.13六、心得體會(huì).14一、設(shè)計(jì)思想1.中綴變后綴表達(dá)式的基本思路：使用一個(gè)棧和一個(gè)數(shù)組（棧是運(yùn)算符棧，數(shù)組是用來(lái)存放后綴表達(dá)式）用于表達(dá)式的轉(zhuǎn)換(1) 定義一個(gè)字符數(shù)組，并輸入一個(gè)中綴表達(dá)式。然后從中綴表達(dá)式中從左往右依次讀入各個(gè)字符。(2) 如果是數(shù)字字符，則直接將它們寫(xiě)入后綴表達(dá)式中即隊(duì)列中。(3) 如果遇到的

2、是開(kāi)括號(hào)“（”，則將它們壓入一個(gè)操作符棧（不需要與棧頂操作符相比較），它表明一個(gè)新的計(jì)算層次的開(kāi)始，在遇到和它匹配的閉括號(hào)“）”時(shí)，將棧中的元素彈出來(lái)并放入后綴表達(dá)式中，直到棧頂元素為“(”時(shí)，將棧頂元素“（”彈出（不需要加入后綴表達(dá)式），表明這一層括號(hào)內(nèi)的操作處理完畢。(4) 如果遇到的是操作符，則將該操作符和操作符棧頂元素比較：當(dāng)所遇到的操作符的優(yōu)先級(jí)小于或等于棧頂元素的優(yōu)先級(jí)時(shí)，則取出棧頂元素放入后綴表達(dá)式，并彈出該棧頂元素，反復(fù)執(zhí)行直到操作符的優(yōu)先級(jí)大于棧頂元素的優(yōu)先級(jí)的時(shí)則將它壓入棧中。(5) 重復(fù)上述步驟直到綴表達(dá)式的結(jié)束符標(biāo)記“#“，彈出棧中所有元素并放入后綴表達(dá)，轉(zhuǎn)換結(jié)束。2.

3、后綴表達(dá)式的計(jì)算的基本思路：使用一個(gè)棧和一個(gè)數(shù)組（棧是運(yùn)算對(duì)象，數(shù)組是用來(lái)存放后綴表達(dá)式）用于表達(dá)式的計(jì)算。從左到右遍歷表達(dá)式的每一個(gè)數(shù)字和符號(hào)，遇到數(shù)字就進(jìn)棧，遇到運(yùn)算符號(hào)，就將棧頂?shù)膬蓚€(gè)數(shù)字出棧，進(jìn)行計(jì)算，運(yùn)算結(jié)果進(jìn)棧，直到獲得最終結(jié)果結(jié)束。3.中綴表達(dá)式求值要把一個(gè)表達(dá)式翻譯成正確求值的一個(gè)機(jī)器指令序列，或者直接對(duì)表達(dá)式求值，首先要能夠正確解釋表達(dá)式，要了解算術(shù)四則運(yùn)算的規(guī)則即：a先乘除后加減； b從左到右計(jì)算；c 先括號(hào)內(nèi)，后括號(hào)外。下表定義的運(yùn)算符之間的關(guān)系: ba+-*/（）#+_*/(#= 為了實(shí)現(xiàn)運(yùn)算符有限算法，在程序中使用了兩個(gè)工作棧。分別是：運(yùn)算符棧OPTR,操作數(shù)棧OPN

4、D.基本思想：（1） 首先置操作數(shù)棧為空棧，表達(dá)式起始符“#”為運(yùn)算符棧的棧底元素；（2） 依次讀入表達(dá)式中每個(gè)字符，若是操作數(shù)則進(jìn)OPND棧，若是運(yùn)算符則和OPTR棧得棧頂運(yùn)算符比較優(yōu)先級(jí)后作相應(yīng)操作。若大于棧頂元素優(yōu)先級(jí)則如棧，若小于棧頂元素優(yōu)先級(jí)則退出和OPND得操作數(shù)進(jìn)行計(jì)算，并把計(jì)算結(jié)果如OPND棧。直至整個(gè)表達(dá)式求值完畢（即OPND棧的棧頂元素和當(dāng)前讀入的字符均為“#”）。二、算法流程圖1中綴變后綴算法流程圖圖2后綴表達(dá)式計(jì)算算法流程圖圖3中綴表達(dá)式計(jì)算算法流程三、源代碼下面給出的是定義Stack.h文件的源代碼：/stack.h#ifndef STACK_H_#define ST

5、ACK_H_class Stackprivate:int top; /定義整形變量enum MAXLEN = 100;/定義長(zhǎng)度為100int arrayMAXLEN;/數(shù)組public:Stack()top = 0;bool empty();bool full();bool pop(int & e);bool push(int e);#endif下面給出的是中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式并求值算法實(shí)現(xiàn)的程序的源代碼： #include #include #include #include using namespace std;class Expression public: Expressio

6、n(); static int Compare(char op); static void ITP(string expression);/中綴轉(zhuǎn)化為后綴 static int Clculate();/計(jì)算表達(dá)式 static vector sResult;/創(chuàng)建矢量字符串 static stack snum; /創(chuàng)建棧的整形變量 ; vector Expression:sResult;/變量sResult所用域?yàn)镋xpression stack Expression:snum; Expression:Expression() sResult.reserve(100);/字符串長(zhǎng)度初始值為10

7、0 int Expression:Compare(char op) /比較字符的優(yōu)先級(jí) int Level = 0; switch(op) case +:case -: Level = 1;break; case *:case /: Level = 2; break; default: break; return Level; void Expression:ITP(string expression) /把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 string:size_type nCount = expression.length(); /字符串長(zhǎng)度賦給nCount string:size_type i

8、ndex = 0; /初始化索引 stack stmp; /創(chuàng)建stmp是一個(gè)棧的對(duì)象 bool flag = false;/標(biāo)志位 stmp.push(); /把壓入棧stmp while( index nCount) /索引小于字符串長(zhǎng)度 if( expressionindex = () stmp.push(); index+; else if( expressionindex = ) while( stmp.top() != () sResult.push_back( string(1, stmp.top() );/把stmp頂元素壓入矢量sResult stmp.pop(); /whi

9、le stmp.pop(); index+; / else if else if( expressionindex = + | expressionindex = - | expressionindex = * | expressionindex = / ) if( expressionindex = - | expressionindex = + ) if(index = 0)/index指向第一個(gè)數(shù) index +; flag = true; /標(biāo)志位為true /if else if( expressionindex-1 = ( )/如果主索引的前一個(gè)數(shù)是（ index+; flag =

10、 true; /標(biāo)志位為true /else if else while( Compare( expressionindex ) = Compare( stmp.top() ) /索引指向字符優(yōu)先級(jí)小于stmp棧頂優(yōu)先級(jí) sResult.push_back(string(1, stmp.top() ); /把stmp頂元素壓入矢量sResult stmp.pop(); /while stmp.push( expressionindex ); / 索引指向字符壓入stmp index+; /else /if else while( Compare( expressionindex ) = 0 &

11、 expressionindex = 9) temp += expressionindex; index +; /while sResult.push_back( temp ); /把temp元素壓入矢量sResult /else /while while(stmp.top() != ) if(stmp.top() = () cout Error in expression endl; exit(-1); sResult.push_back( string(1, stmp.top() ); /把stmp頂元素壓入矢量sResult stmp.pop(); / 中綴轉(zhuǎn)化為后綴 int Expre

12、ssion:Clculate() size_t index = 0;/初始化索引為0 int num1 = 0, num2 = 0; for(index = 0; index 1) & (oper0 = + | oper0 = -) ) snum.push( atoi(sResultindex.c_str() );/矢量字符轉(zhuǎn)換 else switch(oper0) case +: num1 = snum.top(); snum.pop(); num2 = snum.top(); snum.pop(); snum.push( num2 + num1); break; case -: num1

13、= snum.top(); snum.pop(); num2 = snum.top(); snum.pop(); snum.push( num2 - num1); break; case *: num1 = snum.top(); snum.pop(); num2 = snum.top(); snum.pop(); snum.push( num2 * num1); break; case /: num1 = snum.top(); snum.pop(); num2 = snum.top(); snum.pop(); if(num1 = 0) cerr Expression worng! end

14、l; exit(-1); snum.push( num2 / num1); break; default: snum.push( atoi(sResultindex.c_str() ); /矢量字符轉(zhuǎn)換 break; /swith /while int result = snum.top(); 棧snum頂元素賦給整形變量result snum.pop(); return result; int main() string Input; cout please input the expression (Enter key for end) Input;/掃描輸入字符串 Expression:

15、ITP(Input);/中綴表達(dá)式轉(zhuǎn)化為后綴 cout 后綴表達(dá)式: endl; for(size_t index = 0; index Expression:sResult.size(); +index) cout Expression:sResultindex ; cout endl; cout 計(jì)算結(jié)果: endl; cout Expression:Clculate() endl;/輸出計(jì)算結(jié)果 return 0;下面給出的是中綴表達(dá)式求值算法實(shí)現(xiàn)的程序的源代碼：#include #include using namespace std;char Precede(char t1, cha

16、r t2)/判斷t1,t2兩符號(hào)的優(yōu)先關(guān)系(#用#代替)char f;switch(t2) /t1與t2比較case +:case -:if(t1=(| t1=#)f=;/t1;/t1t2break;case *:case /:if(t1=*|t1=/|t1=)f=;/t1t2elsef=;/t1t2break;case (:if(t1=)cout 括號(hào)不匹配 endl;exit( 0 );elsef=;/t1t2break;case ):switch(t1)/與t1比較優(yōu)先級(jí)case (: f = =; /t1=t2break;case #: cout 缺乏左括號(hào) ;/t1t2break;c

17、ase #: switch(t1) /與t1比較優(yōu)先級(jí)case #: f= =;/t1=t2break;case (:cout 缺乏右括號(hào) ;/t1t2return f;bool IsOperator(char c)/判斷c是否為7種運(yùn)算符之一switch(c)case +:case -:case *:case /:case (:case ):case #:return true;default: return false;int Operate(int a, char oper, int b)/做運(yùn)算a theta b,返回運(yùn)算結(jié)果switch(oper)case +:return a+b;

18、case -:return a-b;case *:return a*b;case /: if(b=0) cout Expression worng! endl; return a/b;default:break;int EvaluateExpression()stack OPTR, OPND;/設(shè)置操作數(shù)棧和操作符棧int a,b,d,x;/定義整形變量a,b,d,xchar c;/ 定義字符串變量cOPTR.push(#);/#壓入OPTR棧c=getchar();/當(dāng)前字符用C表示x=OPTR.top();/OPTR棧頂用X表示while(c!=#|x!=#)/ if(IsOperator

19、(c) /判斷c是否為7種運(yùn)算符之一switch(Precede(x,c) 判斷x,c兩符號(hào)的優(yōu)先關(guān)系case:x=OPTR.top();OPTR.pop();b=OPND.top();OPND.pop(); a=OPND.top();OPND.pop(); OPND.push(Operate(a,x,b);/把計(jì)算結(jié)果壓入數(shù)棧else if(c=0&c=0&c=9)/字符C大于0且小于9d = d*10+c-0;/字符串轉(zhuǎn)化為相應(yīng)的值c = getchar();OPND.push(d);elsecout 出現(xiàn)非法字符 endl;exit( 0 );x=OPTR.top();x=OPND.to

20、p();if(OPND.empty()cout 表達(dá)式不正確# endl;exit( 0 );/退出return x;int main()cout 請(qǐng)輸入算術(shù)表達(dá)式,負(fù)數(shù)要用(0-正數(shù))表示，以#號(hào)結(jié)束n;cout 結(jié)果是：EvaluateExpression() endl;return 0;四、運(yùn)行結(jié)果運(yùn)行程序，輸入中綴表達(dá)式結(jié)束后，敲回車鍵顯示后綴表達(dá)式和計(jì)算結(jié)果，如圖4所示：圖4 中綴變后綴表達(dá)式求值的運(yùn)行結(jié)果圖運(yùn)行程序，輸入中綴表達(dá)式以#結(jié)束后，敲回車鍵顯示計(jì)算結(jié)果，如圖5所示：圖5 中綴表達(dá)式的運(yùn)行結(jié)果圖五、遇到的問(wèn)題及解決這部分我主要遇到了如下兩個(gè)問(wèn)題，其內(nèi)容與解決方法如下所列：l 如何將一位數(shù)變成兩位數(shù)解決方案：在各數(shù)字之間用空格隔開(kāi)，并且添加語(yǔ)句，主要思想是當(dāng)?shù)谝粋€(gè)數(shù)字進(jìn)棧后，判斷下一個(gè)進(jìn)棧的元素，若是數(shù)字元素則進(jìn)棧，若是運(yùn)算符，則加空格將其與其他數(shù)字分開(kāi)。l 生成后綴表達(dá)式時(shí)，如何將數(shù)和字符存放在一個(gè)字符串中解決方案：不把字符數(shù)組的數(shù)字都截取出來(lái)，而是把數(shù)字進(jìn)行一個(gè)