数据结构课程设计报告-培训课件.docVIP

数据结构课程设计报告 PAGE PAGE 1 第 PAGE 1页 .. Word资料. 课 程 设 计 报 告 课程设计名称： 数据结构 系 ： 计算机科学系 学生姓名： 李锡会 班 级： 13計算機科學與技術1班 学 号： 1314080901118 成 绩： 指导教师： 肖錦輝老師 开课时间： 2014-2015 学年 第 2 学期 一．设计题目 算术表达式求值 二．主要内容 （所选课题的需求分析，实现功能等） 1、程序能对所输入的表达式作简单的判断，如表达式有错。 2、能处理单目运算符：+、-。 三．课题设计的基本思想，原理和算法描述 （包括课题所用数据结构，界面设计、输入/输出设计，功能模块设计，符号说明等） 对于中缀表达式，一般运算规则如下： 1、先乘方，再乘除，最后加减。 2、同级运算从左算到右。 3、先括号内，再括号外。 操作的符号：+ - * / ^ % (). 根据实际经验，可以对运算符设置统一的优先级，从而方便比较。 上面讨论的+、-为双目运算符，如单目运算符，编程实现时，可在前面加上0而转化为双目运算符。 思路如下： 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．若ch为单目运算符，则在ch前面加上操作符0，也就是将0入pond。 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），结果入opnd栈。 四．源程序及注释 需要用到的头文件有： lk_stack.h node.h utility.h cal.h // cal.h #ifndef __CALCULATOR_H__ #define __CALCULATOR_H__ #include lk_stack.h // 链栈类 templateclass ElemType class Calculator { private: LinkStackElemType opnd; LinkStackchar optr; //char GetChar(); int OperPrior(char op); void Get2Operands (ElemType left,ElemType right); ElemType Operate(ElemType left,char op,ElemType right); bool IsOperator(char ch); public: Calculator(){}; virtual ~Calculator(){}; void Run(); }; templateclass ElemType int CalculatorElemType::OperPrior(char ch) { if(ch == =) return 1; if(ch == ^) return 5; if(ch == (||ch == )) return 2; if(ch == +|| ch == -) return 3; if(ch == *||ch == /||ch == %) return 4; return 0; } templateclass ElemType bool CalculatorElemType::IsOperator(char ch) { if (ch == = || ch == ( || ch == * || ch == /