實驗報告11.8.數(shù)據(jù)結(jié)構(gòu).docVIP

數(shù)據(jù)結(jié)構(gòu)（雙語）項目文檔報告用兩種方式實現(xiàn)表達式自動計算專 業(yè)： 網(wǎng)絡(luò)工程 班 級： 13網(wǎng)絡(luò)1班 指導教師： 吳亞峰 姓 名： 霍國豪 學 號： 201314150113 目 錄一、設(shè)計思想.01二、算法流程圖.02三、源代碼.04四、運行結(jié)果.12五、遇到的問題及解決.13六、心得體會.14一、設(shè)計思想1.中綴變后綴表達式的基本思路：使用一個棧和一個數(shù)組（棧是運算符棧，數(shù)組是用來存放后綴表達式）用于表達式的轉(zhuǎn)換(1) 定義一個字符數(shù)組，并輸入一個中綴表達式。然后從中綴表達式中從左往右依次讀入各個字符。(2) 如果是數(shù)字字符，則直接將它們寫入后綴表達式中即隊列中。(3) 如果遇到的是開括號“（”，則將它們壓入一個操作符棧（不需要與棧頂操作符相比較），它表明一個新的計算層次的開始，在遇到和它匹配的閉括號“）”時，將棧中的元素彈出來并放入后綴表達式中，直到棧頂元素為“(”時，將棧頂元素“（”彈出（不需要加入后綴表達式），表明這一層括號內(nèi)的操作處理完畢。(4) 如果遇到的是操作符，則將該操作符和操作符棧頂元素比較：當所遇到的操作符的優(yōu)先級小于或等于棧頂元素的優(yōu)先級時，則取出棧頂元素放入后綴表達式，并彈出該棧頂元素，反復執(zhí)行直到操作符的優(yōu)先級大于棧頂元素的優(yōu)先級的時則將它壓入棧中。(5) 重復上述步驟直到綴表達式的結(jié)束符標記“#“，彈出棧中所有元素并放入后綴表達，轉(zhuǎn)換結(jié)束。2.后綴表達式的計算的基本思路：使用一個棧和一個數(shù)組（棧是運算對象，數(shù)組是用來存放后綴表達式）用于表達式的計算。從左到右遍歷表達式的每一個數(shù)字和符號，遇到數(shù)字就進棧，遇到運算符號，就將棧頂?shù)膬蓚€數(shù)字出棧，進行計算，運算結(jié)果進棧，直到獲得最終結(jié)果結(jié)束。3.中綴表達式求值要把一個表達式翻譯成正確求值的一個機器指令序列，或者直接對表達式求值，首先要能夠正確解釋表達式，要了解算術(shù)四則運算的規(guī)則即：a先乘除后加減； b從左到右計算；c 先括號內(nèi)，后括號外。下表定義的運算符之間的關(guān)系: ba+-*/（）#+_*/(#= 為了實現(xiàn)運算符有限算法，在程序中使用了兩個工作棧。分別是：運算符棧OPTR,操作數(shù)棧OPND.基本思想：（1） 首先置操作數(shù)棧為空棧，表達式起始符“#”為運算符棧的棧底元素；（2） 依次讀入表達式中每個字符，若是操作數(shù)則進OPND棧，若是運算符則和OPTR棧得棧頂運算符比較優(yōu)先級后作相應操作。若大于棧頂元素優(yōu)先級則如棧，若小于棧頂元素優(yōu)先級則退出和OPND得操作數(shù)進行計算，并把計算結(jié)果如OPND棧。直至整個表達式求值完畢（即OPND棧的棧頂元素和當前讀入的字符均為“#”）。二、算法流程圖1中綴變后綴算法流程圖圖2后綴表達式計算算法流程圖圖3中綴表達式計算算法流程三、源代碼下面給出的是定義Stack.h文件的源代碼：/stack.h#ifndef STACK_H_#define STACK_H_class Stackprivate:int top; /定義整形變量enum MAXLEN = 100;/定義長度為100int arrayMAXLEN;/數(shù)組public:Stack()top = 0;bool empty();bool full();bool pop(int & e);bool push(int e);#endif下面給出的是中綴表達式轉(zhuǎn)化為后綴表達式并求值算法實現(xiàn)的程序的源代碼： #include #include #include #include using namespace std;class Expression public: Expression(); static int Compare(char op); static void ITP(string expression);/中綴轉(zhuǎn)化為后綴 static int Clculate();/計算表達式 static vector sResult;/創(chuàng)建矢量字符串 static stack snum; /創(chuàng)建棧的整形變量 ; vector Expression:sResult;/變量sResult所用域為Expression stack Expression:snum; Expression:Expression() sResult.reserve(100);/字符串長度初始值為100 int Expression:Compare(char op) /比較字符的優(yōu)先級 int Level = 0; switch(op) case +:case -: Level = 1;break; case *:case /: Level = 2; break; default: break; return Level; void Expression:ITP(string expression) /把中綴表達式轉(zhuǎn)換為后綴表達式 string:size_type nCount = expression.length(); /字符串長度賦給nCount string:size_type index = 0; /初始化索引 stack stmp; /創(chuàng)建stmp是一個棧的對象 bool flag = false;/標志位 stmp.push(); /把壓入棧stmp while( index nCount) /索引小于字符串長度 if( expressionindex = () stmp.push(); index+; else if( expressionindex = ) while( stmp.top() != () sResult.push_back( string(1, stmp.top() );/把stmp頂元素壓入矢量sResult stmp.pop(); /while stmp.pop(); index+; / else if else if( expressionindex = + | expressionindex = - | expressionindex = * | expressionindex = / ) if( expressionindex = - | expressionindex = + ) if(index = 0)/index指向第一個數(shù) index +; flag = true; /標志位為true /if else if( expressionindex-1 = ( )/如果主索引的前一個數(shù)是（ index+; flag = true; /標志位為true /else if else while( Compare( expressionindex ) = Compare( stmp.top() ) /索引指向字符優(yōu)先級小于stmp棧頂優(yōu)先級 sResult.push_back(string(1, stmp.top() ); /把stmp頂元素壓入矢量sResult stmp.pop(); /while stmp.push( expressionindex ); / 索引指向字符壓入stmp index+; /else /if else while( Compare( expressionindex ) = 0 & 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 Expression: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 = 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! endl; 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:ITP(Input);/中綴表達式轉(zhuǎn)化為后綴 cout 后綴表達式: endl; for(size_t index = 0; index Expression:sResult.size(); +index) cout Expression:sResultindex ; cout endl; cout 計算結(jié)果: endl; cout Expression:Clculate() endl;/輸出計算結(jié)果 return 0;下面給出的是中綴表達式求值算法實現(xiàn)的程序的源代碼：#include #include using namespace std;char Precede(char t1, char t2)/判斷t1,t2兩符號的優(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 括號不匹配 endl;exit( 0 );elsef=;/t1t2break;case ):switch(t1)/與t1比較優(yōu)先級case (: f = =; /t1=t2break;case #: cout 缺乏左括號 ;/t1t2break;case #: switch(t1) /與t1比較優(yōu)先級case #: f= =;/t1=t2break;case (:cout 缺乏右括號 ;/t1t2return f;bool IsOperator(char c)/判斷c是否為7種運算符之一switch(c)case +:case -:case *:case /:case (:case ):case #:return true;default: return false;int Operate(int a, char oper, int b)/做運算a theta b,返回運算結(jié)果switch(oper)case +:return a+b;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();/當前字符用C表示x=OPTR.top();/OPTR棧頂用X表示while(c!=#|x!=#)/ if(IsOperator(c) /判斷c是否為7種運算符之一switch(Precede(x,c) 判斷x,c兩符號的優(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);/把計算結(jié)果壓入數(shù)棧else if(c=0&c=0&c=9)/字符C大于0且小于9d = d*10+c-0;/字符串轉(zhuǎn)化為相應的值c = getchar();OPND.push(d);elsecout 出現(xiàn)非法字符 endl;exit( 0 );x=OPTR.top();x=OPND.top();if(OPND.empty()cout 表達式不正確# endl;exit( 0 );/退出return x;int main()cout 請輸入算術(shù)表達式,負數(shù)要用(0-正數(shù))表示，以#號結(jié)束n;cout 結(jié)果是：EvaluateExpression() endl;return 0;四、運行結(jié)果運行程序，輸入中綴表達式結(jié)束后，敲回車鍵顯示后綴表達式和計算結(jié)果，如圖4所示：圖4 中綴變后綴表達式求值的運行結(jié)果圖運行程序，輸入中綴表達式以#結(jié)束后，敲回車鍵顯示計算結(jié)果，如圖5所示：圖5 中綴表達式的運行結(jié)果圖五、遇到的問題及解決這部分我主要遇到了如下兩個問題，其內(nèi)容與解決方法如下所列：l 如何將一位數(shù)變成兩位數(shù)解決方案：在各數(shù)字之間用空格隔開，并且添加語句，主要思想是當?shù)谝粋€數(shù)字進棧后，判斷下一個進棧的元素，若是數(shù)字元素則進棧，若是運算符，則加空格將其與其他數(shù)字分開。l 生成后綴表達式時，如何將數(shù)和字符存放在一個字符串中解決方案：不把字符數(shù)組的數(shù)字都截取出來，而是把數(shù)字進行一個