1、數(shù)據(jù)結(jié)構(gòu)與算法分析課程設(shè)計報告課題名稱：帶括號的算術(shù)表達(dá)式求值課題負(fù)責(zé)人名（學(xué)號）：0743111298同組成員名單（角色）： 戴維指導(dǎo)教師：評閱成績：評閱意見：提交報告時間：200 年 月日課程名稱：數(shù)據(jù)結(jié)構(gòu)學(xué)生姓名：戴維學(xué)生學(xué)號：0743111298帶括號的算術(shù)表達(dá)式求值軟件工程專業(yè)學(xué)生戴維指導(dǎo)老師朱宏-25-一、實(shí)驗(yàn)一：帶括號的算術(shù)表達(dá)式求值二、實(shí)驗(yàn)的目的和要求：1 .采用算符優(yōu)先數(shù)算法，能正確求值表達(dá)式；2 .熟練掌握棧的應(yīng)用；3 .熟練掌握計算機(jī)系統(tǒng)的基本操作方法，了解如何編輯、編譯、鏈接和運(yùn)行個C+程序；4 .上機(jī)調(diào)試程序，掌握查錯、排錯使程序能正確運(yùn)行。三、實(shí)驗(yàn)的環(huán)境 ：1 .硬

2、件環(huán)境：Intel(R) Celeron(R)M CPU520 1.60GHz1.60GHz , 0.99Gb內(nèi)存2 .軟件環(huán)環(huán)境：操作系統(tǒng):Microsoft Windows XP版本2002Professinal編譯系統(tǒng)版本：MicroSoft Visual C+6.0,編輯軟件特點(diǎn)等。包括操作系統(tǒng)，編譯系統(tǒng)的版本的特點(diǎn) 四、算法描述：對于帶有括號的算術(shù)表達(dá)式有以下的運(yùn)算法則:1 .先乘方，再乘除，最后加減。2 .同級運(yùn)算從左到右。3 .先括號內(nèi)，再括號外。而運(yùn)算符號的優(yōu)先級別如下表所示：運(yùn)算符=()+ -* / %A優(yōu)先級12345具體實(shí)現(xiàn)如下：1 .先建立兩個堆棧，一個是操作符堆棧，一

3、個為操作數(shù)堆棧。并且將這兩個堆棧先清空，然后在操作符號堆棧當(dāng)中放入一個“="，以便在后面方便判斷表達(dá)式是否結(jié)束。2 .從輸入流當(dāng)中讀取一個字符，循環(huán)執(zhí)行下面的操作：去出操作符號堆棧的棧頂元素，如果棧頂元素是不是“="并且如果當(dāng)前的字符也是“=”的時候，那么表示表達(dá)式已經(jīng)結(jié)束了，當(dāng)前操作數(shù)堆棧的棧頂元素就是表達(dá)式的值。如果當(dāng)前字符不是操作符，就將當(dāng)前字符放回到輸入流當(dāng)中，讀取操作數(shù)， 并且將操作數(shù)加入到操作數(shù)堆棧當(dāng)中，繼續(xù)讀入下一個字符。如果當(dāng)前字符是操作符就進(jìn)行下面的操作：.如果當(dāng)前字符不是“+”或者“-”，則在當(dāng)前字符前面加一個“0”放入到操作數(shù)棧當(dāng)中。如果當(dāng)前字符和操作

4、符的棧頂元素不匹配，例如當(dāng)前字符是“("，而棧頂字符“)”，顯示錯誤信息。如果操作符棧的棧頂元素是“(”并且當(dāng)前字符是“)”，則從操作符棧當(dāng)中取出，去掉括號，然后繼續(xù)讀入下面的字符。如果當(dāng)前字符是“(”，或者操作符棧頂元素的優(yōu)先級別比當(dāng)前字符低，則將當(dāng)前字符放入到操作符棧當(dāng)中。繼續(xù)讀入下一個字符。如果操作符棧頂元素的優(yōu)先級別等于或者大于當(dāng)前字符的優(yōu)先級別，那么就取出操作數(shù)棧的 RIGHT和LEFT元素，從操作符棧當(dāng)中取出OP,然后進(jìn)行操作(LEFT) OP ( RIGHT),結(jié)果進(jìn)入到操作數(shù)棧當(dāng)中五、源程序清單Calculator.h:template<class Data_e

5、lement>class Calculatorprivate :Stack<Data_element> opnd ;/建立一個操作數(shù)的棧Stack<char> optr ;/建立一個操作符的棧bool GetTwoOperands(double &left ,double &right);/從操作數(shù)棧當(dāng)中取出最上面的兩個數(shù)字bool DoOperator(char op);/ run the function "left op right"bool IsOperator(char ch);/判斷傳入的字符是不是一個操作符void

6、 GetChar(char &ch);/從輸入流當(dāng)中讀入一個字符int isp(char op); 堆棧外優(yōu)先數(shù)int icp(char op); 堆棧內(nèi)優(yōu)先數(shù)public :void Run() ; /運(yùn)行函數(shù);template<class Data_element>void Calculator<Data_element>:Run()optr.clear() ; /將操作符棧的所有元素清空opnd.clear() ; /將操作數(shù)棧的所有元素清空optr.push('=') ; /先在操作符棧中傳入一個='號，為了能夠更好的判斷運(yùn)算是否

7、已經(jīng)結(jié)束/'='時，運(yùn)算結(jié)束char ch ;/char priorChar ; /char optrTop ; /Data_element operand ;char op = '0'/管GetChar(ch); /optr.top(optrTop); /當(dāng)從外面的讀入的字符是'='并且棧頂符號也是臨時的一個字符前一個字符操作符棧的棧頂元素/需要被操作的操作數(shù)定義一個操作數(shù)為0',便于操作小數(shù)的運(yùn)得到一個字符得到操作符棧的棧頂元素if(optr.top(optrTop片underflow)/如果操作符號棧為空，拋出錯誤信息cout<

8、;<"表達(dá)式有錯！"<<endl;return;while(optrTop!='='|ch!='=')/通過判斷當(dāng)前的字符和棧頂?shù)淖址渲幸粋€不為“=”的時候,/表示現(xiàn)在運(yùn)算還沒有結(jié)束，所以進(jìn)行下面的操作if(isdigit(ch)11ch='.')/如果當(dāng)先的字符是一個數(shù)字或者當(dāng)前字符是小數(shù)點(diǎn)，那么把該 字符放回到輸入流當(dāng)中，/再把該操作數(shù)讀入，并且放到操作數(shù)棧當(dāng)中去，把前一個字符賦為0,然后再繼續(xù)讀入字符cin.putback(ch);cin>>operand;opnd.push(operan

9、d);priorChar='0'GetChar(ch);else if(!IsOperator(ch)/除了數(shù)字以外應(yīng)該只有操作符，現(xiàn)在進(jìn)行判斷，如果不是數(shù)字, 不是小數(shù)點(diǎn)，/也不是操作符號，說明輸入有錯誤，打印錯誤消息，再不斷的 讀入字符，直到讀到表達(dá)式結(jié)束cout<<"表達(dá)式中出現(xiàn)非法字符!"<<endl;while(cin>>ch,ch!='=');return;elseif(priorChar='='|priorChar='(')&&(ch='

10、+'|ch='-')opnd.push(0);if(isp(optrTop)<icp(ch)/如果操作符棧頂元素的優(yōu)先級別小于當(dāng)前操作符號的優(yōu)先 級別就把當(dāng)前的/字符放到操作符棧當(dāng)中，將當(dāng)前字符賦值給前一個字符，再讀入下一個字符optr.push(ch);priorChar=ch;GetChar(ch);else if(isp(optrTop)>icp(ch)/如果操作符棧頂元素的優(yōu)先級別大于當(dāng)前操作符號，/刪除操作符棧頂元素，在判斷OP是不是操作符號，如果不是就返回optr.top(op);optr.pop();if(!DoOperator(op)retu

11、rn;else if(isp(optrTop)=icp(ch)&&ch=')')/如果棧內(nèi)操作符和棧外操作符的優(yōu)先級別一樣的，并且當(dāng) 前的字符為等號的時候optr.pop();priorChar=')'GetChar(ch);；if(optr.top(optrTop)=underflow)/如果操作符棧為空的話，輸出錯誤消息cout<<"表達(dá)式有錯！"<<endl;return;；if(opnd.top(operand)=underflow | optr.pop() = underflow)/如果操作數(shù)

12、字棧為空或者是操作符號在刪除了棧頂元素厚為空，輸出錯誤信息cout<<"表達(dá)式有錯!"<<endl;return;else/刪除操作數(shù)棧的棧頂元素，如果再刪除操作符棧棧頂元素成功刪除或者能夠成功刪除/操作數(shù)棧的棧頂元素，輸出錯誤信息opnd.pop();if (opnd.pop()=success | optr.pop()=success)cout<<"表達(dá)式有錯！"<<endl;return;cout<<operand<<endl;return;；template<class

13、 Data_element>int Calculator<Data_element>:isp(char op)/棧外操作符的優(yōu)先級判斷int result;switch(op)case '=':result=0;break;case '(':result=1;break;case '"result=7;break;case '*':case '/':case '%':result=5;break;case '+':case '-':result=3

14、;break;case ')':result=8;return result;； template<class Data_element>/操作符棧內(nèi)優(yōu)先級的判斷int Calculator<Data_element>:icp(char op) int result;switch(op)case '=':result=0;break;case '(':result=8;break;case '"result=6;break;case case '/':case '%':re

15、sult=4;break;case '+':case '-':result=2;break;case ')':result=1;return result;；template<class Data_element>bool Calculator<Data_element>:GetTwoOperands(double &x,double &y)/從操作數(shù)棧當(dāng)中得到兩個數(shù)字，如果操作數(shù)字棧或者操作符棧的元素少于兩 個的時候輸出錯誤信息if(opnd.empty()cout<<"表達(dá)式有錯！

16、"<<endl;return false;opnd.top(y);opnd.pop();if(opnd.empty()cout<<"表達(dá)式有錯!"<<endl;return false;opnd.top(x);opnd.pop();return true;；template<class Data_element>bool Calculator<Data_element>:DoOperator(char op)/判斷符號，進(jìn)行相應(yīng)的操作Data_element x,y;bool result=GetTwoO

17、perands(x,y);if(result=true)switch(op)case '+':opnd.push(x+y);break;case '-':opnd.push(x-y);break;case '*':opnd.push(x*y);break;case '/':if(y=0)cout<<"除數(shù)為零！"<<endl;return false;opnd.push(x/y);break;case '%':if(long)y=0) cout<<"

18、除數(shù)為零！"<<endl; return false;opnd.push(long)x % (long)y);break;case '"opnd.push(pow(x,y);return true;else return false;template<class ElemType>void Calculator<ElemType>:GetChar(char &ch)/從輸入流當(dāng)中讀入字符cin>>ch;while(ch=' '11ch='n') cin>>ch;tem

19、plate<class Data_element>bool Calculator<Data element>:IsOperator(char ch)/判斷輸入的字符是不是操作符if(ch='='|ch='('|ch='A'|ch='*'|ch='/'11ch='%'11ch='+'|ch='-'|ch=')')return true;elsereturn false;；LK_STACK.h:template<class N

20、ode_entry>struct Node Node_entry entry; /定義一個結(jié)點(diǎn)元素Node<Node_entry> *next; /定義一個結(jié)點(diǎn)指針Node();/無參數(shù)構(gòu)造函數(shù)Node(Node_entry item, Node<Node_entry> *add_on = NULL); 含參構(gòu)造函數(shù);template<class Stack_entry> class Stack public:Stack(); /無參構(gòu)造函數(shù)bool empty() const; /判斷堆棧是不是為空Error_code push(const Stac

21、k_entry &item); / Error_code pop();/Error code top(Stack entry &item) const; /往堆棧當(dāng)中傳入元素刪除堆棧的棧頂元素得到堆棧的棧頂元素void clear();/清空堆棧的所有元素Stack();/析構(gòu)函數(shù)Stack(const Stack<Stack_entry> &original); 有參數(shù)構(gòu)造函數(shù)void operator =(const Stack<Stack_entry> &original); /操作符重載protected:Node<Stac

22、k_entry> *top_node; /定義一個指針； template<class Node_entry> Node<Node_entry>:Node()構(gòu)造函數(shù) next = NULL;template<class Node_entry>Node<Node_entry>:Node(Node_entry item, Node<Node_entry> *add_on)/含參數(shù)構(gòu)造函數(shù)entry = item;next = add_on;template<class Stack_entry>Stack<Stac

23、k_entry>:Stack()/堆棧的構(gòu)造函數(shù) top_node=NULL;template<class Stack_entry>bool Stack<Stack entry>:empty() const/判斷堆棧是不是為空if(top_node=NULL)return true;elsereturn false;template<class Stack_entry>Error_code Stack<Stack_entry>:push(const Stack_entry &item)/往堆棧中添加元素Node<Stack_e

24、ntry> *new_top = new Node<Stack_entry>(item, top_node);if (new_top = NULL) return overflow;top_node = new_top;return success;template<class Stack_entry>Error_code Stack<Stack_entry>:pop()/刪除堆棧的棧頂元素Node<Stack_entry> *old_top = top_node;if (top_node = NULL) return underflow;

25、top_node = old_top->next;delete old_top;return success;template<class Stack_entry>Error code Stack<Stack entry>:top(Stack entry &item) const/得到堆棧的棧頂元素Error_code result;if(empty()return underflow;elseitem=top_node->entry;return success;template<class Stack_entry>void Stack

26、<Stack_entry>:clear()/清空整個堆棧while (!empty()POP()；template<class Stack_entry>Stack<Stack_entry>:Stack()/析構(gòu)函數(shù)clear();Utility.h:#include<string.h> /standard string operations#include<iostream.h> /standard iostream operations#include<limits.h> /numeric limits#include&

27、lt;math.h>/mathematical functions#include<fstream.h> /file input and output#include<ctype.h>/character classification#include<time.h>/date and time function#include<conio.h>/con input and outputenum Error_codesuccess,fail,underflow,overflow; /enum boolfalse,true;Calculator

28、.cpp:#include"Utility.h"#include"LK_STACK.H"#include"Calculator.h"void main()Calculator<double> s;char iscontinue='Y'while(iscontinue='Y') cout<<"輸入表達(dá)式(以等號"="結(jié)束):"<<endl;s.Run();cout<<"是否繼續(xù)(Y/N)?"cin&

29、gt;>iscontinue;iscontinue=toupper(iscontinue);六、運(yùn)行結(jié)果：1. 一般的整數(shù)操作：3+4*5/2=13輸入表達(dá)式以等號限*吉束八3+4«5/2=13是否繼續(xù)y/N>?2.小數(shù)的計算 425*1+3.25/5=4.93.乘方操作：4人4=2564.取模運(yùn)算:7%3=1"D:VC+6_ OByProjectsCalculator47x3 =1是否繼續(xù)<丫>?5.負(fù)數(shù)運(yùn)算：（-5） *6/2=156.分母為零的檢驗(yàn):7. 一次程序結(jié)束后繼續(xù)下一次:Q38. 一次程序結(jié)束后退出程序:% "D:VC+6.

30、 OXlTProjectsVCalculator：3/0=除數(shù)為零？是否繼續(xù)Y/N?y輸入表達(dá)式以等號"結(jié)束：4/2 =2是否繼續(xù)"槨?村Press any key to continue七、實(shí)驗(yàn)運(yùn)行情況分析（包括算法、運(yùn)行結(jié)果、運(yùn)行環(huán)境等問題的討論（一）算法分析：對于帶有括號的算術(shù)表達(dá)式有以下的運(yùn)算法則：1 .先乘方，再乘除，最后加減。2 .同級運(yùn)算從左到右。3 .先括號內(nèi)，再括號外。而運(yùn)算符號的優(yōu)先級別如下表所示：運(yùn)算符=()+ -* / %A優(yōu)先級12345具體實(shí)現(xiàn)如下：1 .先建立兩個堆棧，一個是操作符堆棧，一個為操作數(shù)堆棧。并且將這兩個堆棧先清空，然后在操作符號堆

31、棧當(dāng)中放入一個“="，以便在后面方便判斷表達(dá)式是否結(jié)束。2 .從輸入流當(dāng)中讀取一個字符，循環(huán)執(zhí)行下面的操作：去出操作符號堆棧的棧頂元素，如果棧頂元素是不是“="并且如果當(dāng)前的字符也是“=”的時候，那么表示表達(dá)式已經(jīng)結(jié)束了，當(dāng)前操作數(shù)堆棧的棧頂元素就是表達(dá)式的值。如果當(dāng)前字符不是操作符，就將當(dāng)前字符放回到輸入流當(dāng)中，讀取操作數(shù)， 并且將操作數(shù)加入到操作數(shù)堆棧當(dāng)中，繼續(xù)讀入下一個字符。如果當(dāng)前字符是操作符就進(jìn)行下面的操作：.如果當(dāng)前字符不是“+”或者“-”，則在當(dāng)前字符前面加一個“0”放入到操作數(shù)棧當(dāng)中。如果當(dāng)前字符和操作符的棧頂元素不匹配，例如當(dāng)前字符是“（"，而棧

32、頂字符“）”，顯示錯誤信息。如果操作符棧的棧頂元素是“（”并且當(dāng)前字符是“）”，則從操作符棧當(dāng)中取出，去掉括號，然后繼續(xù)讀入下面的字符。如果當(dāng)前字符是“（”，或者操作符棧頂元素的優(yōu)先級別比當(dāng)前字符低，則將當(dāng)前字符放入到操作符棧當(dāng)中。繼續(xù)讀入下一個字符。如果操作符棧頂元素的優(yōu)先級別等于或者大于當(dāng)前字符的優(yōu)先級別，那么就取出操作數(shù)棧的 RIGHT和LEFT元素，從操作符棧當(dāng)中取出OP,然后進(jìn)行操作（LEFT） OP （ RIGHT）,結(jié)果進(jìn)入到操作數(shù)棧當(dāng)中（二）運(yùn)行結(jié)果分析：1 .對一般的整數(shù)，小數(shù)進(jìn)行操作時，只要先輸入一個準(zhǔn)確的表達(dá)式子即可，當(dāng)計算結(jié)束后，屏幕上會顯示計算結(jié)果，并且征求是否還要繼續(xù)進(jìn)行運(yùn)算。SIm 3小數(shù)運(yùn)算:乘方運(yùn)算:取模運(yùn)算:負(fù)數(shù)運(yùn)算:e -D:VC-H-6. 0IyProjectsCaC-5>«6/