数据结构课程设计--算术表达式求值

《数据结构课程设计--算术表达式求值》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、计算机科学系《数据结构课程设计》报告课题名称：算术表达式求值16目录1.问题描述-----------------------------------------------------------32.基本要求-----------------------------------------------------------33.工具/准备工作----------------------------------------------------34.分析与实现------------------------------------------

2、--------------45.课程设计体会与感悟------------------------------------------16161．问题描述从键盘上输入中缀算术表达式，包括括号，计算出表达式的值。2.基本要求（1）程序能对所输入的表达式做简单的判断，如表达式有错，能给适当提示。（2）能处理单目运算符：+，-。3.工具/准备工作在开始项目之前，应回顾复习相关内容。需要一台计算机装有visualC++。4.分析与实现对于中缀表达式，一般运算规则如下：（1）先乘方，再乘除，最后加减；（2）同级运算从左算到右；（3）先括号内再括号外；（4）

3、用到的头文件”utility.h”,”lk_stack.h”,”node.h”,”calculator.h”.根据实践经验，可以对运算符设置统一的优先级，从而方便比较。表中给出了包括加、减、乘、除、求余、左括号、右括号和分界符的优先级。运算符‘=’‘（’、‘）’‘+’、‘—’‘*’、‘/’‘%’‘^’优先级12245上面讨论的的+、—为双目运算符，如为单目运算符，编程实现时，可在前面加上0而转化为双目运算符。如在+、—的前一个字符（如当前字符不是运算符时，规定用0表示）为‘=’或‘（’，则为单目运算符。16具体实现算法时，可设置两个工作栈，一个为操

4、作栈，一个为操作符栈optr，另外一个为操作数栈opnd,算法基本思路如下：（1）将optr栈和opnd栈清空，在optr栈中加入一个‘=‘。（2）从输入流获取一字符ch,循环执行步骤（3）至步骤（5）直到求出表达式的值为止。（3）取出optr的栈顶optrTop,当optrTop=‘=‘且ch=’=‘时，整个表达式求值完毕，这时opnd栈的栈顶元素为表达式的值。（4）若ch不是操作符，则字符放回输入流（cin.putback）,读操作数operand；将operand加入opnd栈，读入下一个字符ch。（5）如ch是操作符，按如下方式进行处理：a

5、.如果ch为单目运算符，则在ch前面加上操作数0，也就是将0入opnd栈；b.如果optrTop与ch不匹配，例如optrTop=‘）‘且ch=’（‘，显示错误信息；c.如果optrTop=‘（‘且ch=’）‘，则从optr退出栈顶的’（‘，去括号，然后从输入流中读入字符并送入ch；d.如果ch=’(’活optrTop比ch的优先级低，则ch入optr栈，从输入中取下一字符ch；e.如果optrTop大于或等于ch的优先级，则从opnd栈退出left和right，从optr栈退出theta,形成运算指令（left）theta(right),结果如o

6、pnd栈。对于界面处理：（1）用文件流建立一个小小的界面，美化处理一些操作，文件名为dd.txt//dd.txt文档内容*******************欢迎进入运算界面********************请选择：****1.开始运算**2.退出界面*****16对于运算处理：（1）通过运用栈和队列的特性，实现各种功能。本类通过一系列的扩展实现各种出现的运算情况处理//calculator.h#ifndefCALCULATOR_H#defineCALCULATOR_H#include"lk_stack.h"template

7、mType>classCalculator{private:LinkStackopnd;LinkStackoptr;charGetChar()//从输入流中跳过空格，换行符及制表符获取一字符{charc;cin>>c;returnc;}intOperPrior(charop);//要自己写的函数voidGet2Operands(ElemType&left,ElemType&right);//要自己写的函数ElemTypeOperate(ElemTypeleft,charop,ElemTyperight);//要自己写

8、的函数boolIsOperator(charch);//要自己写的函数16public:Calculator(){};vi