《带括号的表达式求值》课程设计报告.doc

数据结构与算法分析课程设计报告课题名称： 带括号的算术表达式求值 课题负责人名（学号）： 0743111298 同组成员名单（角色）： 戴维指导教师： 评阅成绩： 评阅意见： 提交报告时间：200 年 月 日带括号的算术表达式求值软件工程 专业学生 戴维 指导老师 朱宏 一、实验一:带括号的算术表达式求值二、实验的目的和要求:1.采用算符优先数算法,能正确求值表达式;2.熟练掌握栈的应用;3.熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一个C+程序;4.上机调试程序,掌握查错、排错使程序能正确运行。三、实验的环境:1.硬件环境:Intel(R) Celeron(R)M CPU 520 1.60GHz 1.60GHz , 0.99Gb内存2.软件环环境: 操作系统：Microsoft Windows XP Professinal 版本2002 编译系统版本：MicroSoft Visual C+6.0包括操作系统,编译系统的版本的特点,编辑软件特点等。四、算法描述:对于带有括号的算术表达式有以下的运算法则：1先乘方，再乘除，最后加减。2同级运算从左到右。3先括号内，再括号外。而运算符号的优先级别如下表所示：运算符= （） + -* / % 优先级1 2 3 4 5具体实现如下：1先建立两个堆栈，一个是操作符堆栈，一个为操作数堆栈。并且将这两个堆栈先清空，然后在操作符号堆栈当中放入一个“=”，以便在后面方便判断表达式是否结束。2从输入流当中读取一个字符，循环执行下面的操作：去出操作符号堆栈的栈顶元素，如果栈顶元素是不是“=”并且如果当前的字符也是“=”的时候，那么表示表达式已经结束了，当前操作数堆栈的栈顶元素就是表达式的值。如果当前字符不是操作符，就将当前字符放回到输入流当中，读取操作数，并且将操作数加入到操作数堆栈当中，继续读入下一个字符。如果当前字符是操作符就进行下面的操作：如果当前字符不是“+”或者“-”，则在当前字符前面加一个“0”放入到操作数栈当中。如果当前字符和操作符的栈顶元素不匹配，例如当前字符是“（”，而栈顶字符“）”，显示错误信息。如果操作符栈的栈顶元素是“（”并且当前字符是“）”，则从操作符栈当中取出，去掉括号，然后继续读入下面的字符。如果当前字符是“（”，或者操作符栈顶元素的优先级别比当前字符低，则将当前字符放入到操作符栈当中。继续读入下一个字符。如果操作符栈顶元素的优先级别等于或者大于当前字符的优先级别，那么就取出操作数栈的RIGHT 和LEFT元素，从操作符栈当中取出OP，然后进行操作（LEFT）OP（RIGHT），结果进入到操作数栈当中.五、源程序清单:Calculator.h:templateclass Calculator private : Stack opnd ; /建立一个操作数的栈Stack optr ; /建立一个操作符的栈bool GetTwoOperands(double &left ,double &right) ; /从操作数栈当中取出最上面的两个数字bool DoOperator(char op) ; / run the function left op rightbool IsOperator(char ch) ;/判断传入的字符是不是一个操作符 void GetChar(char &ch) ; /从输入流当中读入一个字符 int isp(char op); /堆栈外优先数 int icp(char op); /堆栈内优先数public :void Run() ; /运行函数 ;templatevoid Calculator:Run() optr.clear() ; / 将操作符栈的所有元素清空opnd.clear() ; / 将操作数栈的所有元素清空optr.push(=) ; / 先在操作符栈中传入一个=号，为了能够更好的判断运算是否已经结束 /当从外面的读入的字符是=并且栈顶符号也是=时，运算结束char ch ; / 临时的一个字符char priorChar ; / 前一个字符char optrTop ; / 操作符栈的栈顶元素Data_element operand ; / 需要被操作的操作数 char op = 0; /定义一个操作数为0，便于操作小数的运算 GetChar(ch); /得到一个字符optr.top(optrTop); /得到操作符栈的栈顶元素if(optr.top(optrTop)=underflow)/如果操作符号栈为空，抛出错误信息cout表达式有错!operand;opnd.push(operand);priorChar=0;GetChar(ch);else if(!IsOperator(ch)/除了数字以外应该只有操作符，现在进行判断，如果不是数字，不是小数点，/也不是操作符号，说明输入有错误，打印错误消息，再不断的读入字符，直到读到表达式结束cout表达式中出现非法字符!ch,ch!=); return;elseif(priorChar=|priorChar=()&(ch=+|ch=-)opnd.push(0);if(isp(optrTop)icp(ch) /如果操作符栈顶元素的优先级别大于当前操作符号， /删除操作符栈顶元素，在判断OP是不是操作符号，如果不是就返回optr.top(op);optr.pop();if(!DoOperator(op)return;else if(isp(optrTop)=icp(ch)&ch=)/如果栈内操作符和栈外操作符的优先级别一样的，并且当前的字符为等号的时候optr.pop(); priorChar=); GetChar(ch);if(optr.top(optrTop)=underflow) /如果操作符栈为空的话，输出错误消息cout表达式有错!endl;return; if(opnd.top(operand)=underflow | optr.pop() = underflow) /如果操作数字栈为空或者是操作符号在删除了栈顶元素厚为空，输出错误信息cout表达式有错!endl;return; else /删除操作数栈的栈顶元素，如果再删除操作符栈栈顶元素成功删除或者能够成功删除 /操作数栈的栈顶元素，输出错误信息opnd.pop();if (opnd.pop()=success | optr.pop()=success)cout表达式有错!endl;return;coutoperandendl;return;templateint Calculator:isp(char op)/栈外操作符的优先级判断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;break;case ):result=8;return result;template/操作符栈内优先级的判断int Calculator:icp(char op)int result;switch(op)case =:result=0;break;case (:result=8;break;case :result=6;break;case *:case /:case %:result=4;break;case +:case -:result=2;break;case ):result=1; return result;templatebool Calculator:GetTwoOperands(double &x,double &y)/从操作数栈当中得到两个数字，如果操作数字栈或者操作符栈的元素少于两个的时候输出错误信息if(opnd.empty()cout表达式有错!endl;return false;opnd.top(y);opnd.pop();if(opnd.empty()cout表达式有错!endl;return false;opnd.top(x);opnd.pop();return true;templatebool Calculator:DoOperator(char op)/判断符号，进行相应的操作Data_element x,y;bool result=GetTwoOperands(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除数为零!endl;return false;opnd.push(x/y);break;case %:if(long)y=0)cout除数为零!endl;return false;opnd.push(long)x % (long)y);break;case :opnd.push(pow(x,y);return true;else return false;templatevoid Calculator:GetChar(char &ch)/从输入流当中读入字符cinch;while(ch= |ch=n)cinch;templatebool Calculator:IsOperator(char ch)/判断输入的字符是不是操作符if(ch=|ch=(|ch=|ch=*|ch=/|ch=%|ch=+|ch=-|ch=)return true;else return false;LK_STACK.h:templatestruct Node Node_entry entry; /定义一个结点元素 Node *next; /定义一个结点指针 Node(); /无参数构造函数 Node(Node_entry item, Node *add_on = NULL); /含参构造函数;templateclass Stack public: Stack(); /无参构造函数 bool empty() const; /判断堆栈是不是为空 Error_code push(const Stack_entry &item); /往堆栈当中传入元素 Error_code pop(); /删除堆栈的栈顶元素 Error_code top(Stack_entry &item) const; /得到堆栈的栈顶元素 void clear(); /清空堆栈的所有元素 Stack(); /析构函数 Stack(const Stack &original); /有参数构造函数 void operator =(const Stack &original); /操作符重载protected: Node *top_node; /定义一个指针;templateNode:Node()/构造函数 next = NULL;templateNode:Node(Node_entry item, Node *add_on)/含参数构造函数 entry = item; next = add_on;templateStack:Stack()/堆栈的构造函数 top_node=NULL;templatebool Stack:empty() const/判断堆栈是不是为空 if(top_node=NULL) return true; else return false;templateError_code Stack:push(const Stack_entry &item)/往堆栈中添加元素 Node *new_top = new Node(item, top_node); if (new_top = NULL) return overflow; top_node = new_top; return success;templateError_code Stack:pop()/删除堆栈的栈顶元素 Node *old_top = top_node; if (top_node = NULL) return underflow; top_node = old_top-next; delete old_top; return success;templateError_code Stack:top(Stack_entry &item) const/得到堆栈的栈顶元素 Error_code result; if(empty() return underflow; else item=top_node-entry; return success; templatevoid Stack:clear() /清空整个堆栈 while (!empty() pop();templateStack:Stack()/析构函数clear();Utility.h:#include /standard string operations#include /standard iostream operations#include /numeric limits#include /mathematical functions#include /file input and output#include /character classification#include /date and time function#include /con input and outputenum Error_codesuccess,fail,underflow,overflow;/enum boolfalse,true;Calculator.cpp:#includeUtility.h#includeLK_STACK.H#includeCalculator.hvoid main()Calculator s;char iscontinue=Y;while(iscontinue=Y)cout输入表达式(以等号“=”结束):endl;s.Run();coutiscontinue;iscontinue=toupper(iscontinue);六、运行结果:1.一般的整数操作:3+4*5/2=132.小数的计算:4.25*1+3.25/5=4.93.乘方操作:44=2564.取模运算:7%3=1 5.负数运算：（-5）*6/2=156分母为零的检验：7一次程序结束后继续下一次：8一次程序结束后退出程序：七、实验运行情况分析(包括算法、运行结果、运行环境等问题的讨论)。（一）算法分析：对于带有括号的算术表达式有以下的运算法则：1先乘方，再乘除，最后加减。2同级运算从左到右。3先括号内，再括号外。而运算符号的优先级别如下表所示：运算符= （） + -* / % 优先级1 2 3 4 5具体实现如下：1先建立两个堆栈，一个是操作符堆栈，一个为操作数堆栈。并且将这两个堆栈先清空，然后在操作符号堆栈当中放入一个“=”，以便在后面方便判断表达式是否结束。2从输入流当中读取一个字符，循环执行下面的操作：去出操作符号堆栈的栈顶元素，如果栈顶元素是不是“=”并且如果当前的字符也是“=”的时候，那么表示表达式已经结束了，当前操作数堆栈的栈顶元素就是表达式的值。如果当前字符不是操作符，就将当前字符放回到输入流当中，读取操作数，并且将操作数加入到操作数堆栈当中，继续读入下一个字符。如果当前字符是操作符就进行下面的操作：如果当前字符不是“+”或者“-”，则在当前字符前面加一个“0”放入到操作数栈当中。如果当前字符和操作符的栈顶元素不匹配，例如当前字符是“（”，而栈顶字符“）”，显示错误信息。如果操作符栈的栈顶元素是“（”并且当前字符是“）”，则从操作符栈当中取出，去掉括号，然后继续读入下面的字符。如果当前字符是“（”，或者操作符栈顶元素的优先级别比当前字符低，则将当前字符放入到操作符栈当中。继续读入下一个字符。如果操作符栈顶元素的优先级别等于或者大于当前字符的优先级别，那么就取出操作数栈的RIGHT 和LEFT元素，从操作符栈当中取出OP，然后进行操作（LEFT）OP（RIGHT），结果进入到操作数栈当中.（二）运行结果分析：1对一般的整数，小数进行操作时，只要先输入一个准确的表达式子即可，当计算结束后，屏幕上会显示计算结果，并且征求是否还要继续进行运算。小数运算：乘方运算：取模运算：负数运算：2但是如果在运算过程当中出现了非法的字符，或者经过判断，表达式没有意义，那么在屏幕上就会打印出错误消息：3在结束一次运算过后，系统会提示你是否进行下一次运算，如果你选择是，那么就会提示你继续输入表达式：4：但是如果结束了一次运算后不想在继续进行运算，那么在输入了“N”过后，系统提醒你退出：（三）运行环境等问题的讨论：Visual C+是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+