数据结构表达式求值完整篇(含实验报告)

1、

实验目的和要求

（1）深入理解栈的特点及其描述方法。

（2）能够在两种存储结构上实现栈抽象数据类型实现。 （3）掌握栈的几个典型应用算法，能灵活应用栈解决实际问题。

2、 概要设计

【定义所有抽象数据类型、自定义函数间的调用关系图，自定义函数的功能描述和流程图，以及主程序的流程图。】

开始 定义运算符和操作数栈并初 始化 并fflush(stdin)清除缓存 输入每个字符并执行相应的条件语句入栈出栈 //比较OPTR的栈顶元素和ch的优先级 char Precede (SElemType_OPTR top, While(1) Y EvaluateExpression( ) //运算并将结果出栈 Operate 输出结果

3、 调试分析

【(1) 调试过程中遇到的问题是如何解决的以及对设计与实现中关键点的回顾讨论和分析；(2) 算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；(3) 经验和体会等。】

1.栈的定义、初始化、出栈进栈、取栈顶元素等步骤不难就先把结构打好了 2.操作数和运算符分别入不同的栈 char->int 进操作数栈

先考虑了小于10的整数直接进栈,重点是运算符的优先级这块函数的编写 3前面的都听简单的，就是小数编写这块想了很久，

将单个字符转为整数后还要定一个double p;使依次输入的数成一个小数->p. 在小数入栈使要考虑放在那条if语句中，防止在运算结果入栈后p再次入栈，又定义了int flag;通过flag的值判定p是否入栈。并且成功入栈后p,q都要回到初始状态。小数解决 4.负数部分

讨论一开始就有负数和运算符后面有负数的情况。（比较容易）

右图重点 。

定义了low做判定符号的标志。如果在运算符后输入负号则low=-1(将p入栈时入栈的是p*low)，继续输入ch。

总结：

我觉得写的好的地方在于定义了flag,low分别作为小数入栈和负号与减号区别的条件。第一次写这么长的代码，还有就是将输入的字符再转到小数这段代码可以留着很有用。开始考虑的大整数想麻烦了，直接用double 难度降低了很多

4、 测试数据与结果

输入 1--2# -1-2# -1--2# 3.66+4.34# 2*2+4--3^2# 3.66*2+3-4# 1+3-4*5/2+3.666# 输出 3.000 -3.000 1.000 8.000 -1.000 6.320 -2.339 说明 减负数 两负数 小数 长串+乘方 【列出你的测试结果，包括输入和输出。测试数据应该完整和严格，最好多于需求分析中所列。】

序号 1 2 3 4 5 6 7 5、

附录

【给出每部分的源代码（必须要有一定量的注释）。】

/* common.h */ #include \#include \#include \#include \

/*其他函数的声明*/

double EvaluateExpression ( ); //算数表达式求值的算法优先算法

char Precede (SElemType_OPTR top, char ch); //比较OPTR的栈顶元素和ch的优先级

double Operate (SElemType_OPND a, SElemType_OPTR theta, SElemType_OPND b); //运算

//栈基本操作的函数声明

void OPTR_InitStack(Sqstack_OPTR&s); //运算符栈初始化 void OPND_InitStack(Sqstack_OPND&s); //操作数栈初始化

char OPTR_GetTop(Sqstack_OPTR s); //取运算符的栈顶元素 double OPND_GetTop(Sqstack_OPND s); //取操作数的栈顶元素

void OPTR_Push(Sqstack_OPTR&s,SElemType_OPTR e); //入栈 void OPND_Push(Sqstack_OPND&s,SElemType_OPND e); //入栈

void OPTR_Pop(Sqstack_OPTR&s,SElemType_OPTR&e); //出栈 void OPND_Pop(Sqstack_OPND&s,SElemType_OPND&e); //出栈

/*基本操作函数的实现*/ #include \#include \#include \

//运算符栈初始化

void OPTR_InitStack(Sqstack_OPTR&s) {

s.base=new SElemType_OPTR[MAXSIZE]; if(!s.base)

printf(\运算符栈存储分配失败!\\n\ s.top=s.base;

s.stacksize=MAXSIZE; }

//操作数栈初始化

void OPND_InitStack(Sqstack_OPND&s) {

s.base=new SElemType_OPND[MAXSIZE]; if(!s.base)

printf(\操作数栈存储分配失败!\\n\ s.top=s.base;

s.stacksize=MAXSIZE; }

//取操作符的栈顶元素

char OPTR_GetTop(Sqstack_OPTR s) {

if(s.top!=s.base)

return *(s.top-1);

return 0; }

//取运算数的栈顶元素

double OPND_GetTop(Sqstack_OPND s) {

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构表达式求值完整篇(含实验报告)在线全文阅读。