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

课程名称：数据结构 学生姓名：戴维 学生学号：0743111298 《数据结构与算法分析》课程 课名称： 带括号的算术达式求值 课题负责人名（学号）： 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: template class Calculator { private : Stack opnd ; //建立一个操作数的栈 Stack optr ; //建立一个操作符的栈 bool GetTwoOperands(double &left ,double &right) ; //从操作数栈当中取出最上面的两个数字 bool DoOperator(char op) ; // run the function "left op right" bool IsOperator(char ch) ; //判断传入的字符是不是一个操作符 void GetChar(char &ch) ; //从输入流当中读入一个字符 int isp(char op); //堆栈外优先数 int icp(char op); //堆栈内优先数 public : void Run() ; //运行#函数# }; template void 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; } else { 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(optrTop)==underflow) //如果操作符栈为空的话，输出错误消息 { cout<<"表达式有错!"< int 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; }; template bool Calculator::GetTwoOperands(double &x,double &y) //从操作数栈当中得到两个数字，如果操作数字栈或者操作符栈的元素少于两个的时候输出错误信息 { if(opnd.empty()) { cout<<"表达式有错!"< bool 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<<"除数为零!"< void Calculator::GetChar(char &ch) //从输入流当中读入字符 { cin>>ch; while(ch==' '||ch=='\n') cin>>ch; }; template bool Calculator::IsOperator(char ch) //判断输入的字符是不是操作符 { if(ch=='='||ch=='('||ch=='^'||ch=='*'|| ch=='/'||ch=='%'||ch=='+'||ch=='-'||ch==')') return true; else return false; }; LK_STACK.h: template struct Node { Node_entry entry; //定义一个结点元素 Node *next; //定义一个结点指针 Node(); //无参数构造函数 Node(Node_entry item, Node *add_on = NULL); //含参构造函数 }; template class 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; //定义一个指针 }; template Node::Node()//构造函数 { next = NULL; } template Node::Node(Node_entry item, Node *add_on) //含参数构造函数 { entry = item; next = add_on; } template Stack::Stack() //堆栈的构造函数 { top_node=NULL; } template bool Stack::empty() const //判断堆栈是不是为空 { if(top_node==NULL) return true; else return false; } template Error_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; } template Error_code Stack::pop() //删除堆栈的栈顶元素 { Node *old_top = top_node; if (top_node == NULL) return underflow; top_node = old_top->next; delete old_top; return success; } template Error_code Stack::top(Stack_entry &item) const //得到堆栈的栈顶元素 { Error_code result; if(empty()) return underflow; else{ item=top_node->entry; return success; } } template void Stack::clear() //清空整个堆栈 { while (!empty()) pop(); } template Stack::~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 output enum Error_code{success,fail,underflow,overflow}; //enum bool{false,true}; Calculator.cpp: #include"Utility.h" #include"LK_STACK.H" #include"Calculator.h" void main() { Calculator s; char iscontinue='Y'; while(iscontinue=='Y') { cout<<"输入表达式(以等号“=”结束):"<>iscontinue; iscontinue=toupper(iscontinue); } } 六、运行结果: 1.一般的整数操作:3+4*5/2=13 2.小数的计算:4.25*1+3.25/5=4.9 3.乘方操作:4^4=256 4.取模运算:7%3=1 5.负数运算：（-5）*6/2=15 6．分母为零的检验： 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++已成为专业程序员进行软件开发的首选工具。 Visual C++6.0不仅是一个C++编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrated development environment,IDE）。Visual C++6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具，是c/c++程序开发的首选工具。 总结 1。从中学到的： 经过了自己的努力，参考了许多的资料，自己总算是独立完成了这个程序设计。虽然还是存在着很多很多的问题，但是我觉得自己已经努力了，那么就很欣慰了。 通过这个程序，自己把以前学过的C++知识进行了一些复习，把已经忘记的知识又重新运用了起来。虽然现在在学JAVA，但是C++也同样的重要。在复习的同时也不断地学习新的东西。以前不是很理解

模板

个人简介word模板免费下载关于员工迟到处罚通告模板康奈尔office模板下载康奈尔 笔记本 模板 下载软件方案模板免费下载

，现在经过了这个程序设计，已经稍微对模板有了了解。同时在这个程序里面也用到了堆栈和队列，通过这次地运用，自己对堆栈和队列用法有了进一步地了解，同时也意识到了堆栈和队列在程序设计中的重要性。这个程序设计也让我很清楚地知道了数据结构在程序设计中是多么重要，有了很好的算法设计过后，我们的程序会显得更加的简单明了，也使程序的效率高了很多。 相信以后还有很多这样的机会设计程序，经过这次的设计自己已经有了一定的经验，相信在以后的设计之中，一定会做的更好的。 2．程序的特色： ⑴这个程序除了能够进行一般的整数运算以外，还可以进行小数的运算；除了加减乘除以外，还可以进行乘方，取模运算，和对负数进行操作。 ⑵本程序有处理异常了功能，如果输入了非法操作符的话，屏幕会输出错误信息来提醒你。而且，这个程序可以连续进行多次运算。 3．不足： ⑴这个程序的界面是最原始的操作界面，看起来不是很美观。 ⑵本程序的功能还不够齐全，比如，不能进行未知数的操作。 ⑶程序写的很冗长，没有用到很多高级的语法。 -2- -23-