四川大学计算机学院数据结构及算法分析实验报告
PAGE \* MERGEFORMAT87
《 数据结构与算法 》课程设计
指导老师：班级： 姓名：学号：
算术表达式求值问题描述从键盘上输入中缀算数表达式，包括括号，计算粗话表达式的值。二、基本要求程序对所输出的表达式做出简单的判断，如表达式有错，能给出适当的提示能处理单目运算符：+和—三、工具/准备工作在开始做课程设计项目前，应回顾或复习相关内容。需要一台计算机，其内安装有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_templatestruct Node{ElemType data;Node *next;Node();Node(ElemType item,Node *link=NULL);};templateNode::Node(){ next = NULL;}templateNode::Node(ElemType item, Node *link){ data = item; next = link;}#endif _NODE_H_//文件lk_stack.h#ifndef _LINK_STACK_H_#define _LINK_STACK_H_#include "utility.h"#include "node.h"templateclass LinkStack{protected:Node *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 LinkStack ©);LinkStack&operator=(const LinkStack
ChitGPT提问
