四川大学计算机学院数据结构与算法分析实验报告.docx

《数据结构与算法》课程设计指导老师：班级：姓名：学号：算术表达式求值问题描述从键盘上输入中缀算数表达式，包括括号，计算粗话表达式的值。二、基本要求程序对所输出的表达式做出简单的判断，如表达式有错，能给出适当的提示能处理单目运算符：+和—三、工具/准备工作在开始做课程设计项目前，应回顾或复习相关内容。需要一台计算机，其内安装有Microsoft Visual Studio 2010的集成开发环境软件四、分析与实现对中缀表达式，一般运算规则如下：先乘方，再乘除，最后加减同级运算从左算到右先算括号内，再算括号外根据实践经验，可以对运算符设置统一的优先级，从而方便比较。如下表：运算符 = （） +- */% ^优先级 1 2 3 4 5单目运算符：+，—（可以看成0+/—个数）双目运算符：+，—（在+或—的前一个字符（当前一个不是运算符时，规定用‘0’表示））为‘=’，‘（’，则为单目运算符。 具体实现算法时，可设置两个工作栈，一个为操作符栈optr(operator),另一个为操作数栈opnd(operand),算法基本工作思路如下：将optr栈和opnd栈清空，在optr栈中加入一个‘=’从输入流获取一字符ch，循环执行（3）~（5）直到求出表达式的值为止。取出optr的栈顶optrTop，当optrTop=‘=’且ch=‘=’时，整个表达式求值完毕，这时opnd栈顶元素为表达式的值。若ch不是操作符，则将字符放回输入流（cin.putback），读操作数operand；将operand加入opnd栈，读入下一个字符ch。若ch是操作符，按如下方式进行处理如果ch为单目运算符，则在ch前面加上操作数0，也就是将0入opnd栈。如果optrTop与ch不匹配，例如optrTop=’）’且ch=‘（’,显示错误信息。如果optrTop=‘（’且ch=‘）’，则从optr栈退出栈顶的‘（’，去括号，然后从输入流中读入字符并送入ch如果ch=‘（’或optrTop比ch的优先级低，则ch入optr栈，从optr栈退出theta，形成运算指令（left）theta(right),结果入opnd栈。源代码：//文件node.h#ifndef _NODE_H_#define _NODE_H_templateclass ElemTypestruct Node{ElemType data;NodeElemType *next;Node();Node(ElemType item,NodeElemType *link=NULL);};templateclass ElemTypeNodeElemType::Node(){ next = NULL;}templateclass ElemTypeNodeElemType::Node(ElemType item, NodeElemType *link){ data = item; next = link;}#endif _NODE_H_//文件lk_stack.h#ifndef _LINK_STACK_H_#define _LINK_STACK_H_#include utility.h#include node.htemplateclass ElemTypeclass LinkStack{protected:NodeElemType *top;void Init();public:LinkStack();int Length() const; bool Empty() const;void Clear();void Traverse(void (* visit)(const ElemType )) const;StatusCode Push(const ElemType e);StatusCode Pop(ElemType e);StatusCode Top(ElemType e) const;LinkStack(const LinkStackElemType copy);LinkStackElemTypeoperator=(const LinkStackElemType copy);};templateclass ElemTypevoid LinkStackElemType::Init(){top=NULL;}templateclass ElemTypeLinkStackElemType::LinkStack(){Init(); }template class ElemTypeint LinkStackElemType::Length() const{int count = 0;for ( NodeElemType *tm