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

《数据结构与算法分析》课程设计报告课题名称：带括号的算术表达式求值课题负责人名（学号）：0743111298同组成员名单（角色）：戴维指导教师：评阅成绩：评阅意见：提交报告时间：200年月日课程名称：数据结构学生姓名：戴维学生学号：0743111298-1-带括号的算术表达式求值软件工程专业学生戴维指导老师朱宏一、实验一:带括号的算术表达式求值二、实验的目的和要求:1.采用算符优先数算法,能正确求值表达式;2.熟练掌握栈的应用;3.熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一个C++程序;4.上机调试程序,掌握查错、排错使程序能正确运行。三、实验的环境:1.硬件环境:Intel(R)Celeron(R)MCPU520@1.60GHz1.60GHz,0.99Gb内存2.软件环环境:操作系统：MicrosoftWindowsXPProfessinal版本2002编译系统版本：MicroSoftVisualC++6.0包括操作系统,编译系统的版本的特点,编辑软件特点等。四、算法描述:课程名称：数据结构学生姓名：戴维学生学号：0743111298-2-对于带有括号的算术表达式有以下的运算法则：1．先乘方，再乘除，最后加减。2．同级运算从左到右。3．先括号内，再括号外。而运算符号的优先级别如下表所示：运算符=（）+-*/%^优先级12345具体实现如下：1．先建立两个堆栈，一个是操作符堆栈，一个为操作数堆栈。并且将这两个堆栈先清空，然后在操作符号堆栈当中放入一个“=”，以便在后面方便判断表达式是否结束。2．从输入流当中读取一个字符，循环执行下面的操作：⑴去出操作符号堆栈的栈顶元素，如果栈顶元素是不是“=”并且如果当前的字符也是“=”的时候，那么表示表达式已经结束了，当前操作数堆栈的栈顶元素就是表达式的值。⑵如果当前字符不是操作符，就将当前字符放回到输入流当中，读取操作数，并且将操作数加入到操作数堆栈当中，继续读入下一个字符。⑶如果当前字符是操作符就进行下面的操作：①．如果当前字符不是“+”或者“-”，则在当前字符前面加一个“0”放入到操作数栈当中。②如果当前字符和操作符的栈顶元素不匹配，例如当前字符是“（”，而栈顶字符“）”，显示错误信息。③如果操作符栈的栈顶元素是“（”并且当前字符是“）”，则从操作符栈当中取出，去掉括号，然后继续读入下面的字符。④如果当前字符是“（”，或者操作符栈顶元素的优先级别比当前字符低，则将当前字符放入到操作符栈当中。继续读入下一个字符。⑤如果操作符栈顶元素的优先级别等于或者大于当前字符的优先级别，那么就取出操作数栈的RIGHT和LEFT元素，从操作符栈当中取出OP，然后进行操作（LEFT）OP（RIGHT），结果进入到操作数栈当中.课程名称：数据结构学生姓名：戴维学生学号：0743111298-3-五、源程序清单:Calculator.h:templateclassData_elementclassCalculator{private:StackData_elementopnd;//建立一个操作数的栈Stackcharoptr;//建立一个操作符的栈boolGetTwoOperands(double&left,double&right);//从操作数栈当中取出最上面的两个数字boolDoOperator(charop);//runthefunctionleftoprightboolIsOperator(charch);//判断传入的字符是不是一个操作符voidGetChar(char&ch);//从输入流当中读入一个字符intisp(charop);//堆栈外优先数inticp(charop);//堆栈内优先数public:voidRun();//运行函数};templateclassData_elementvoidCalculatorData_element::Run(){optr.clear();//将操作符栈的所有元素清空opnd.clear();//将操作数栈的所有元素清空optr.push('=');//先在操作符栈中传入一个‘=’号，为了能够更好课程名称：数据结构学生姓名：戴维学生学号：0743111298-4-的判断运算是否已经结束//当从外面的读入的字符是‘=’并且栈顶符号也是‘=’时，运算结束charch;//临时的一个字符charpriorChar;//前一个字符charoptrTop;//操作符栈的栈顶元素Data_elementoperand;//需要被操作的操作数charop='0';//定义一个操作数为‘0’，便于操作小数的运算GetChar(ch);//得到一个字符optr.top(optrTop);//得到操作符栈的栈顶元素if(optr.top(optrTop)==underflow)//如果操作符号栈为空，抛出错误信息{cout表达式有错!endl;return;}while(optrTop!='='||ch!='=')//通过判断当前的字符和栈顶的字符其中一个不为“=”的时候，//表示现在运算还没有结束，所以进行下面的操作{if(isdigit(ch)||ch=='.')//如果当先的字符是一个数字或者当前字符是小数点，那么把该字符放回到输入流当中，//再把该操作数读入，并且放到操作数栈当中去，把前一个字符课程名称：数据结构学生姓名：戴维学生学号：0743111298-5-赋为0，然后再继续读入字符{cin.putback(ch);cinoperand;opnd.push(operand);priorChar='0';GetChar(ch);}elseif(!IsOperator(ch))//除了数字以外应该只有操作符，现在进行判断，如果不是数字，不是小数点，//也不是操作符号，说明输入有错误，打印错误消息，再不断的读入字符，直到读到表达式结束{cout表达式中出现非法字符!endl;while(cinch,ch!='=');return;}else{if((priorChar=='='||priorChar=='(')&&(ch=='+'||ch=='-'))opnd.push课程名称：数据结构学生姓名：戴维学生学号：0743111298-6-(0);if(isp(optrTop)icp(ch))//如果操作符栈顶元素的优先级别小于当前操作符号的优先级别就把当前的//字符放到操作符栈当中，将当前字符赋值给前一个字符，再读入下一个字符{optr.push(ch);priorChar=ch;GetChar(ch);}elseif(isp(optrTop)icp(ch))//如果操作符栈顶元素的优先级别大于当前操作符号，//删除操作符栈顶元素，在判断OP是不是操作符号，如果不是就返回{optr.top(op);optr.pop();if(!DoOperator(op))return;}elseif(isp(optrTop)==icp(ch)&&ch==')')//如果栈内操作符和栈外操作符的优先级别一样的，并且当前的字符为等号的时候{课程名称：数据结构学生姓名：戴维学生学号：0743111298-7-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;课程名称：数据结构学生姓名：戴维学生学号：0743111298-8-}coutoperandendl;return;}};templateclassData_elementintCalculatorData_element::isp(charop)//栈外操作符的优先级判断{intresult;switch(op){case'=':result=0;break;case'(':result=1;break;case'^':result=7;break;case'*':case'/':case'%':result=5;break;case'+':课程名称：数据结构学生姓名：戴维学生学号：0743111298-9-case'-':result=3;break;case')':result=8;}returnresult;};templateclassData_element//操作符栈内优先级的判断intCalculatorData_element::icp(charop){intresult;switch(op){case'=':result=0;break;case'(':result=8;break;case'^':result=6;break;case'*':case'/':case'%':result=4;课程名称：数据结构学生姓名：戴维学生学号：0743111298-10-break;case'+':case'-':result=2;break;case')':result=1;}returnresult;};templateclassData_elementboolCalculatorData_element::GetTwoOperands(double&x,double&y)//从操作数栈当中得到两个数字，如果操作数字栈或者操作符栈的元素少于两个的时候输出错误信息{if(opnd.empty()){cout表达式有错!endl;returnfalse;}opnd.top(y);opnd.pop();if(opnd.empty()){cout表达式有错!endl;returnfalse;}opnd.top(x);opnd.pop();课程名称：数据结构学生姓名：戴维学生学号：0743111298-11-returntrue;};templateclassData_elementboolCalculatorData_element::DoOperator(charop)//判断符号，进行相应的操作{Data_elementx,y;boolresult=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;returnfalse;}课程名称：数据结构学生姓名：戴维学生学号：0743111298-12-opnd.push(x/y);break;case'%':if((long)y==0){cout除数为零!endl;returnfalse;}opnd.push((long)x%(long)y);break;case'^':opnd.push(pow(x,y));}returntrue;}elsereturnfalse;};templateclassElemTypevoidCalculatorElemType::GetChar(char&ch)//从输入流当中读入字符{cinch;w