《四川大学计算机学院数据结构与算法分析实验报告》由会员分享，可在线阅读，更多相关《四川大学计算机学院数据结构与算法分析实验报告（77页珍藏版）》请在金锄头文库上搜索。
1、1 数据结构与算法 课程设计指导老师：班级： 2姓名：学号：1.算术表达式求值一、 问题描述从键盘上输入中缀算数表达式，包括括号，计算粗话表达式的值。二 、 基 本 要 求1) 程序对所输出的表达式做出简单的判断，如表达式有错，能给出适当的提示2) 能处理单目运算符：+和三 、 工 具 /准 备 工 作在开始做课程设计项目前，应回顾或复习相关内容。需要一台计算机，其内安装有 Microsoft Visual Studio 2010 的集成开发环境软件四 、 分 析 与 实 现对中缀表达式，一般运算规则如下：1) 先乘方，再乘除，最后加减2) 同级运算从左算到右3) 先算括号内，再算括号外根据实
2、践经验，可以对运算符设置统一的优先级，从而方便比较。如下表：运算符 = （） +- */% 3优先级 1 2 3 4 5单目运算符：+，（可以看成 0+/个数）双目运算符：+，（在+或的前一个字符（当前一个不是运算符时，规定用0表示） ）为= ，（ ，则为单目运算符。具体实现算法时，可设置两个工作栈，一个为操作符栈 optr(operator),另一个为操作数栈opnd(operand),算法基本工作思路如下：1) 将 optr 栈和 opnd 栈清空，在 optr 栈中加入一个=2) 从输入流获取一字符 ch，循环执行（3）（5）直到求出表达式的值为止。3) 取出 optr 的栈顶 optr
3、Top，当 optrTop=且 ch=时，整个表达式求值完毕，这时 opnd栈顶元素为表达式的值。4) 若 ch 不是操作符，则将字符放回输入流（cin.putback） ，读操作数 operand；将 operand 加入opnd 栈，读入下一个字符 ch。5) 若 ch 是操作符，按如下方式进行处理i. 如果 ch 为单目运算符，则在 ch 前面加上操作数 0，也就是将 0 入 opnd 栈。ii. 如果 optrTop 与 ch 不匹配，例如 optrTop=） 且 ch=（,显示错误信息。iii. 如果 optrTop=（且 ch=） ，则从 optr 栈退出栈顶的（ ，去括号，然后从
4、输入流中读入字符并送入 chiv. 如果 ch=（或 optrTop 比 ch 的优先级低，则 ch 入 optr 栈，从 optr 栈退出 theta，形成运算指令（left）theta(right),结果入 opnd 栈。源代码： /文件 node.h#ifndef _NODE_H_#define _NODE_H_templatestruct Node4ElemType data;Node *next;Node();Node(ElemType item,Node *link=NULL);templateNode:Node()next = NULL;templateNode:Node(Ele
5、mType 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.htemplateclass LinkStack5protected:Node *top;void Init();public:LinkStack();int Length() const; bool Empty() const;void Clear();void Traverse(void
6、(* visit)(const ElemType StatusCode Push(const ElemType StatusCode Pop(ElemType StatusCode Top(ElemType LinkStack(const LinkStack LinkStack;templatevoid LinkStack:Init()top=NULL;templateLinkStack:LinkStack()6Init(); template int LinkStack:Length() constint count = 0;for ( Node *tmpPtr = top; tmpPtr
7、!= NULL; tmpPtr = tmpPtr-next)count+;return count;templatebool LinkStack:Empty() constreturn top=NULL;templatevoid LinkStack:Clear()ElemType tmpElem;7while(!Empty()Pop(tmpElem);templatevoid LinkStack:Traverse(void (* visit)(const ElemType &) constNode *tmpPtr;LinkStack tmpS;for(tmpPtr=top;tmpPtr!=NU
8、LL;tmpPtr-next)tmpS.Push(tmpPtr-data);for(tmpPtr=tmpS.top;tmpPtr!=NULL;tmpPtr-next)(* visit)(tmpPtr-data);templateStatusCode LinkStack:Push(const ElemType &e)Node *new_top=new Node(e,top);8if(new_top=NULL)return OVER_FLOW;elsetop=new_top;return SUCCESS;templateStatusCode LinkStack:Top(ElemType & e)
9、constif(Empty()return UNDER_FLOW;elsee=top-data;return SUCCESS;9templateStatusCode LinkStack:Pop(ElemType &e)if(Empty()return UNDER_FLOW;elseNode *old_top=top;e=old_top-data;top=old_top-next;delete old_top;return SUCCESS;templateLinkStack:LinkStack(const LinkStack ©)if(copy.Empty()Init();else10t
10、op=new Node(copy.top-data);Node *buttomPtr=top;for(Node *tmp=copy.top-next;tmpPtr!=NuLL;tmpPtr!=NULL;tmpPtr=tmpPtr-next)buttomPtr-next=new Node(tmpPtr-data)buttomPtr=buttomptr-next;templateLinkStack&LinkStack:operator=(const LinkStack ©)if(©!=this)if(copy.Empty()Init();elseClear();top=new No
11、de(copy.top-data);Node *buttomPtr=top;11for(Node *tmpPtr=copy.top-next;tmpPtr!=Null;tmpPtr=tmpPtr-next)buttomPtr-next=new Node(tmpPtr-data);buttomPtr=buttomPtr-next;return *this;#endif _LINK_STACK_H_ /文件路径名: calculator.h/ 文件路径名: calculatorcalculator.h #ifndef _CALCULATOR_H_#define _CALCULATOR_H_#inc
12、lude lk_stack.h / 链栈类/ 计算器类templateclass Calculatorprivate:12LinkStack opnd; / 操作数栈LinkStack optr; / 操作符栈int OperPrior(char op); / 操作符优先级void Get2Operands(ElemType ElemType Operate(ElemType left, char op, ElemType right); bool IsOperator(char ch);/ 判断 ch 是否为操作符 public:Calculator(); / 无参数的构造函数virtual
13、 Calculator(); / 析构函数void Run(); / 运算表达式;templateint Calculator:OperPrior(char op)int prior; / 优先级if (op = =) prior = 1; / =优先级为 1else if (op = ( | op = ) prior = 2; / (优先级为 2else if (op = + | op = -) prior = 3; / +-优先级为 3else if (op = * | op = /| op = %) prior = 4;/ */%优先级为 4else if (op = ) prior =
14、 5;return prior; templatevoid Calculator:Get2Operands(ElemType &left, ElemType &right)13if (opnd.Pop(right) = UNDER_FLOW) throw Error(表达式有错!); if (opnd.Pop(left) = UNDER_FLOW) throw Error(表达式有错!);templateElemType Calculator:Operate(ElemType left, char op, ElemType right)ElemType result;if (op = +) r
15、esult = left + right; / 加法运算else if (op = -) result = left - right; / 减法运算else if (op = *) result = left * right; / 乘法运算else if (op = / else if (op = / else if (op = % else if (op = % else if (op = ) result = pow(left, right); / 乘方运算return result; / 返回 resulttemplatebool Calculator:IsOperator(char ch)if (ch = = | ch = ( | ch = | ch = * |ch = / | ch =% | ch = + | ch= - | ch = ) return true;e
