湖南大学数据结构试验3四则运算表达式求值.doc

实验四 四则运算表达式的求值 一、需求分析 result is 159.00 二、概要设计 1．ADT LinkList? { ?? 数据对象：D?? 数据关系：…Dm（m0），对任意j不等于k（1=j,k=m）有Dj和Dk的交集为空，且任意的i（1=i=m）,唯一存在数据元素Xi属于Di，有root,Xi属于H； （3）.对应于D-{root}的划分，H-{root,Xi,…,root,Xm}有唯一的一个划分H1,H2，…Hm（m0），对任意j不等于k（1=j,k=m）有Hj和Hk的交集为空，且对任意i（1=i=m）， Hi是Di上的二元关系，（Di，{Hi}）是一棵符合定义的树，称为根root的子树。 ?? 基本操作： int CrtNode(stack BiTree PTR, char *c)??????? 操作结果：void CrtSubTree(stack BiTree PTR, char c) 初始条件：二叉树根节点存在 操作结果：建立二叉树的子树 void CrtExptree(BiTree T, char exp[]) 初始条件：二叉树存在 操作结果：根据字符串exp的内容构建表达式树T void PostOrderTraverse(BiTree T, char * exp ,int count) 初始条件：二叉树不为空 操作结果：后序遍历二叉树，依据T-len的值，把T-data中的字符依次添加到当前exp字符串的尾端 ?} ADT LinkList 2．本程序包含三个基本模块 （1）主程序模块：其中又包括和 （2）线性表模块：实现线性表的抽象数据类型 （3）元素结构单元模块：定义线性表每个元素的结构 三、详细设计 1．元素类型，类型typedef struct BiTNode { TElemType data; int len; //data字符串中字符的个数 struct BiTNode * lchild, * rchild; }BiTNode, *BiTree; 栈类型：c++标准容器stack容器 2．根据特点即为该的名称该基本操作具体实现如下 Status Push(SqStack S, SElemtype e) S.base =(SElemtype*)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemtype)); if(!S.base)exit(OVERFLOW);//存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; } Status Pop(SqStack S, SElemtype e) {//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if(S.top==S.base) return ERROR; e=*--S.top; return OK; } Status IsDigital(char ch) { if(ch=0ch=9) { return 1; //是数字字母 } return 0; //不是数字字母 } Status InitStack(SqStack S) { S.base = (SElemtype *)malloc(STACK_INIT_SIZE*sizeof(SElemtype)); if (! S.base) exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) {int len; len=S.top-S.base; return len; //获得堆栈元素的个数 //填空 } int EvalValue(char *ch, SqStack S) { int i=0; SElemtype result=0; char a; a=ch[i]; while(IsDigital(a)) { result=10*result+(int)(a-48); a=ch[++i]; } Push(S, result); return i; } void EvalExpr(char ch, SqStack S) { int i;