数据结构实验实验2-基于栈的算术表达式求值算法报告书.doc

得分： 北 京 林 业 大 学2013学年2014学年第1学期数据结构A实验报告书专 业： 数字媒体艺术 班 级： 姓 名： 学 号： 实验地点： 机房N09 任课教师： 实验题目： 基于栈的算术表达式求值算法 实验环境： 学习完了数据结构第三章内容栈和队列 实验目的：1掌握栈的定义及实现；2掌握利用栈求解算术表达式的方法。实验内容：通过修改完善教材中的算法3.1-3.4，利用栈来实现算术表达式求值的算法。对算法中调用的几个函数要给出其实现过程：(1) 函数In(c)：判断c是否为运算符；(2) 函数Precede(t1,t2)：判断运算符t1和t2的优先级；(3) 函数Operate(a,theta,b)：对a和b进行二元运算theta。程序运行时，输入合法的算术表达式（中间值及最终结果要在09之间，可以包括加减乘除和括号），便可输出相应的计算结果。如下图：实现方法、实验结果及结论分析等：（一）实现方法1. 所用数据结构的定义及其相关说明（相关结构体或类的定义及其含义） /定义一个栈类型的结构体 typedef struct SqStackSElemType * base; /* 在栈构造之前和销毁之后，base的值为NULL */SElemType * top; /* 栈顶指针*/int stacksize; /* 当前已分配的存储空间，以元素为单位*/SqStack; 2. 自定义函数的名称及其功能说明Status InitStack(SqStack &S) /* 构造一个空栈S */Status GetTop(SqStack &S, SElemType &e) /* 若栈不空，则用e返回S的栈顶元素，并返回e；否则返回ERROR */Status Push(SqStack &S, SElemType e) /* 插入元素e为新的栈顶元素*/Status Pop(SqStack &S, char &e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回e；否则返回ERROR */char Precede(char t1, char t2) /* 判断两符号的优先关系*/ int In(char c) /* 判断c是否为运算符*/char Operate(char a, char theta, char b) /进行运算的函数char EvaluateExpression() /输入运算表达式并计算3. 主要功能算法的时间复杂度Status InitStack(SqStack &S) O(1);Status GetTop(SqStack &S, SElemType &e) O(1);Status Push(SqStack &S, SElemType e) O(1);Status Pop(SqStack &S, char &e) O(1);char Precede(char t1, char t2) O(1); int In(char c) O(1);char Operate(char a, char theta, char b) O(1);char EvaluateExpression() O(n);4. 实验任务书中要求画的流程图 结果输出主函数main（）表达式输入调用EvaluateExpression()图2.1总体规划图结束输入表达式进操作数栈OPND,同时栈顶上移YYN判断栈顶优先级Case: 退栈并将运算结果入栈N开始是运算符？判断字符不是#?同时栈顶字符不是#？“#”结束运算操作数出栈计算结果，栈顶上移并把结果返回Y（二）实验结果个位数以内的求解算术表达式结果： （三）结论分析1. 问题与解决方法通过编写算术表达式的程序实现了个位数以内算术表达式求解。利用栈和队列分别存储运算符和字符然后比较优先级实现运算输出结果。2. 收获和体会 算术表达式求解运用了栈和队列相应知识，我从中深刻体会到了栈和队列的深刻意义，能够灵活运用栈和队列来运用到其他领域。栈是先进后出而队列是先进先出，故我深刻认识到了相应的含义。3. 尚存在的问题由所面对的问题直接想到运用到栈和队列仍有难度。需要通过不断练习来进一步完善。算法如下：头文件stack.h#include #include #include #include using namespace std;/* stack.h 栈的顺序存储表示*/#define STACK_INIT_SIZE 100 /* 存储空间初始分配量*/#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef char SElemType;#define MAX_CHAR_LEN 200typedef int TYPE_Status;typedef struct SqStackSElemType * base; /* 在栈构造之前和销毁之后，base的值为NULL */SElemType * top; /* 栈顶指针*/int stacksize; /* 当前已分配的存储空间，以元素为单位*/SqStack; /* 顺序栈*/Status InitStack(SqStack &S) /* 构造一个空栈S */S.base = new SElemTypeSTACK_INIT_SIZE;if( !S.base )exit(OVERFLOW); /* 存储分配失败*/S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;Status GetTop(SqStack &S, SElemType &e) /* 若栈不空，则用e返回S的栈顶元素，并返回e；否则返回ERROR */if(S.top = S.base)return ERROR;e = *(S.top-1);return e;Status Push(SqStack &S, SElemType e) /* 插入元素e为新的栈顶元素*/if(S.top-S.base = S.stacksize) /* 栈满*/cout栈满，无法压栈!endl;return ERROR;*S.top = e;S.top+;return e;Status Pop(SqStack &S, char &e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */if(S.top = S.base)return ERROR;e = *-S.top;return e;Cpp文件calculator.cpp#includestack.h /自己定义的栈的头文件char Precede(char t1, char t2) /* 根据教科书表.1，判断两符号的优先关系*/char f;switch(t2)case +:if(t1=( | t1=#) f=;break;case -:if(t1=( | t1=#) f=;break;case *:if(t1=* | t1=/|t1=) f=; else f=; else f=;break;case (:if(t1!=) f=; break;case #:if(t1!=() if(t1=#) f=; else f=; break;return f;int In(char c) /* 判断c是否为运算符*/switch(c)case +: return OK;case -: return OK;case *: return OK;case /: return OK;case (: return OK;case ): return OK;case #: return OK;default: return ERROR;char Operate(char a, char theta, char b) /进行运算的函数char c=0;a = a - 48;b = b - 48;switch(theta)case +: c = a+b+48; break;case -: c = a-b+48; break;case *: c = (a*b)+48; break;case /: c =( a/b)+48; break;return c;char EvaluateExpression() SqStack OPND,OPTR;char ch;char a,b,x,theta;SElemType e;InitStack(OPTR);Push(OPTR,#);InitStack(OPND);cinch;while(ch!=#|GetTop(OPTR,e)!=#)if(!In(ch)Push(OPND,ch);cinch;elseswitch(Precede(GetTop(OPTR,e),ch)casech;break;case:Pop(OPTR,