《《带括号的表达式求值》课程设计报告》由会员分享，可在线阅读，更多相关《《带括号的表达式求值》课程设计报告（26页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法分析课程设计报告课题名称： 带括号的算术表达式求值 课题负责人名（学号）： 0743111298 同组成员名单（角色）： 戴维指导教师： 评阅成绩： 评阅意见： 提交报告时间：200 年 月 日带括号的算术表达式求值软件工程 专业学生 戴维 指导老师 朱宏 一、实验一:带括号的算术表达式求值二、实验的目的和要求:1.采用算符优先数算法,能正确求值表达式;2.熟练掌握栈的应用;3.熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一个C+程序;4.上机调试程序,掌握查错、排错使程序能正确运行。三、实验的环境:1.硬件环境:Intel(R) Celeron(R)M CP
2、U 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先建立两个堆栈，一个是操作符堆栈，一个为操作数堆栈。并且将这两个堆栈先清空，然后在操作
3、符号堆栈当中放入一个“=”，以便在后面方便判断表达式是否结束。2从输入流当中读取一个字符，循环执行下面的操作：去出操作符号堆栈的栈顶元素，如果栈顶元素是不是“=”并且如果当前的字符也是“=”的时候，那么表示表达式已经结束了，当前操作数堆栈的栈顶元素就是表达式的值。如果当前字符不是操作符，就将当前字符放回到输入流当中，读取操作数，并且将操作数加入到操作数堆栈当中，继续读入下一个字符。如果当前字符是操作符就进行下面的操作：如果当前字符不是“+”或者“-”，则在当前字符前面加一个“0”放入到操作数栈当中。如果当前字符和操作符的栈顶元素不匹配，例如当前字符是“（”，而栈顶字符“）”，显示错误信息。如果
4、操作符栈的栈顶元素是“（”并且当前字符是“）”，则从操作符栈当中取出，去掉括号，然后继续读入下面的字符。如果当前字符是“（”，或者操作符栈顶元素的优先级别比当前字符低，则将当前字符放入到操作符栈当中。继续读入下一个字符。如果操作符栈顶元素的优先级别等于或者大于当前字符的优先级别，那么就取出操作数栈的RIGHT 和LEFT元素，从操作符栈当中取出OP，然后进行操作（LEFT）OP（RIGHT），结果进入到操作数栈当中.五、源程序清单:Calculator.h:templateclass Calculator private : Stack opnd ; /建立一个操作数的栈Stack optr
5、; /建立一个操作符的栈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() ; /运行函数
6、;templatevoid Calculator:Run() optr.clear() ; / 将操作符栈的所有元素清空opnd.clear() ; / 将操作数栈的所有元素清空optr.push(=) ; / 先在操作符栈中传入一个=号，为了能够更好的判断运算是否已经结束 /当从外面的读入的字符是=并且栈顶符号也是=时，运算结束char ch ; / 临时的一个字符char priorChar ; / 前一个字符char optrTop ; / 操作符栈的栈顶元素Data_element operand ; / 需要被操作的操作数 char op = 0; /定义一个操作数为0，便于操作小数
7、的运算 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;else
8、if(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(opt
9、rTop)=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表达式有错!e
10、ndl;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 %:re
