数据结构实验报告 图

第第页数据结构实验报告图

问题描述：

四那么运算表达式求值，将四那么运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。

一、需求分析：

1、本程序是利用二叉树后序遍历来实现表达式的转换，同时可以运用试验三的结果来求解后缀表达式的值。

2、输入输出格式：

输入格式：在字符界面上输入一个中缀表达式，回车表示结束。

请输入表达式：

输入一个中缀表达式

输出格式：假如该中缀表达式正确，那么在字符界面上输出其后缀表达

式，其中后缀表达式中两相邻操作数之间利用空格隔开;如

果不正确，在字符界面上输出表达式错误提示。

逆波兰表达式为：

3、测试用例

输入：21+23*(12-6)

输出：2123126-*+输出逆波兰表达式运算结果为：输出运算后的结果

二、概要设计：

抽象数据类型

二叉树类BiTree

算法的基本思想

依据题目要求，利用栈计算，和二叉树存储，来计算表达式

该算法的基本思想是：

先利用栈进行计算，然后用二叉树进行存储，和试验三算法一样来计算逆波兰表达式的值

程序的流程

程序由三个模块组成：

(1)输入模块：输入一个运算式

(2)计算模块：利用栈进行表达式的计算，二叉树来存储。(3)输出模块：屏幕上显示出后缀表达式和运算结果。

三、具体设计

物理数据类型

程序含有两个类，其中栈不再赘述，另一个类为二叉树classBiTree包含私有成员structBiTreeNode，根节点BiTreeNode*T;索引inde*;intnumber_of_point优先级比较函数compare(chara,charb);生成树的函数voidInorderCreate(BiTreeNode*T,charstr[30][10],intstart,intend);判断数字函数boolIsNumber(chara);求值函数doubleOperate(BiTreeNode*T);还有显示后缀表达式的函数voiddisplay(BiTreeNode*T);而公有成员函数那么是对私有函数的重载，为方便运用，由于函数中普遍运用了递归的算法。

算法的时空分析

此算法利用栈和二叉树来实现，故次算法的的时间繁复度为(N)。

输入和输出的格式

输入格式：请输入表达式：

输入一个中缀表达式//回车

输出格式：逆波兰表达式为：

输出逆波兰表达式

运算结果为：输出运算后的结果

四、调试分析

略。

五、测试结果

本试验的测试结果截图如下：

六、用户运用说明(可选)

1、本程序的运行环境为windows操作系统，执行文件为biaodashi.e*e2、运行程序时

提示输入表达式

本程序可以将中缀表达式转换为后缀表达式后在计算出运算式的结果。提示：请输入表达式：

输出

提示：逆波兰表达式为：

运算结果：

七、试验心得(可选)

本次试验过程比较繁复，由于书上的`知识掌控的还不是很牢靠，所以现在试验做起来有点儿吃力。本试验主要是通过与同学的争论和课后查阅资料来完成的，虽然有些地方还不是很懂，但基本上能完成此次试验的内容。而且通过本次试验，加深了对二叉树算法的了解。

附录(试验代码)：

#include

#include

#include

#include

#include

#include

#defineSTACK_INIT_SIZE100

#defineDATA_SIZE10

#defineSTACKINCREMENT10

#defineOK1

#defineTRUE1

#defineFALSE0

#defineERROR0

#defineOVERFLOW-2

usingnamespacestd;

typedeffloatSElemtype;

typedefintStatus;

typedefchar*TElemType;

typedefstructBiTNode{

TElemTypedata;

intlen;//data字符串中字符的个数

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

typedefstruct

{

SElemtype*base;

SElemtype*top;

intstacksize;

}SqStack;

StatusIsDigital(charch)

{if(ch=0ch=9)

{return1;//是数字字母

}

return0;//不是数字字母

}

intCrtNode(stackPTR,char*c)

{

BiTNode*T;

inti=0;

T=(BiTNode*)malloc(sizeof(BiTNode));

T-data=(char*)malloc(DATA_SIZE*sizeof(char));

while(IsDigital(c[i]))

{T-data[i]=c[i];

i++;}

T-len=i;

T-lchild=T-rchild=NULL;

PTR.push(T);

returni;

}

voidCrtSubTree(stackPTR,charc)

{BiTNode*T;

T=(BiTNode*)malloc(sizeof(BiTNode));

T-data=(char*)malloc(DATA_SIZE*sizeof(char));

T-data[0]=c;

T-len=1;

T-rchild=PTR.top();//先右子树，否那么运算次序反了

PTR.pop();

T-lchild=PTR.top();

PTR.pop();

PTR.push(T);

}

charsymbol[5][5]={{,,,,},//符号优先级

{,,,,},

{,,,,},

{,,,,},

{,,,,=}};

intsym2num(chars)//返回符号对应优先级矩阵位置{switch(s)

{

case+:return0;break;

case-:return1;break;

case*:return2;break;

case/:return3;break;

case#:return4;break;

}

}

charPrecede(chara,charb)//返回符号优先级

{return(symbol[sym2num(a)][sym2num(b)]);}

voidCrtE*ptree(BiTreeT,chare*p[])

{//依据字符串e*p的内容构建表达式树T

stackPTR;//存放表达式树中的节点指针

stackOPTR;//存放操作符

charop;

inti=0;

OPTR.push(#);

op=OPTR.top();

while(!((e*p[i]==#)(OPTR.top()==#)))//与

{

if(IsDigital(e*p[i]))

{//建立叶子节点并入栈PTR

i+=CrtNode(PTR,e*p[i]);

}

elseif(e*p[i]==)

i++;

else{

switch(e*p[i])

{

case(:{