1、 课程设计课程设计 表达式类型的实现表达式类型的实现 2008 8 年年 7 月月 3 3 日日 数据结构课程设计报告数据结构课程设计报告 第第 2 页页 共共 34 页页 一、一、需求分析【需求分析【课程设计要求课程设计要求】 【问题的描述】【问题的描述】 一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现 基于二叉树表示的算术表达式 Expression 的操作。 【基本要求】【基本要求】 【一】 【一】 【必做部分】必做部分】 假设算术表达式 Expression 内可以含有变量（a-z）,常量（0-9）和二元 运算符（+，-，*，/，（乘幂） ） 。实现以下操作： （1
2、）ReadExpr(E)以字符序列的形式输入语法正确的前缀表达式并构造 表达式 E。 （2）WriteExpr(E)用带括号的中缀表达式输出表达式 E。 （3）Assign(V，c)实现对变量 V 的赋值（V=c） ，变量的初值为 0。 （4）Value(E)对算术表达式 E 求值。 （5）CompoundExpr(p,E1,E2)构造一个新的复合表达式（E1）p（E2） 。 【二】【二】 【选做部分】【选做部分】 （1）以表达式的原书写形式输入，支持大于 0 的正整数常量； （2）增加常数合并操作 MergeConst(E)合并表达式 E 中所有常数运算。例 如，对表达式 E=(2+3-a)
3、*(b+3*4)进行合并常数的操作后，求得 E=(5-a)*(b+12) 【测试数据】【测试数据】 1) 分别输入 0；a;-91;+a*bc;+*5x2*8x;+*3*2x2x6 并输出。 2) 每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。 3) 还有很多测试的数据，详细请见附上的文件 Test.txt。 二、二、概要概要设计设计 1 1、数据类型的声明：、数据类型的声明： 在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助 存储结构存储结构 /*/*头文件以及存储结构头文件以及存储结构*/*/
4、#include #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef int Status; 数据结构课程设计报告数据结构课程设计报告 第第 3 页页 共共 34 页页 2 2、表达式、表达式的抽象数据类型定义的抽象数据类型定义 ADT ExpressionADT Expression 数据对象 D：D 是具有数值的常量 C 和没有数值的变量 V； 数据关系：R=|V,CD, 表示由运算 符 P 结合起来的表达式 E 基
5、本操作： Status Input_Expr(Status Input_Expr( 操作结果：运算符运算求值，参数 opr1,opr2 为常量，opr 为运算符，根据不同 的运算符，实现不同的运算，返回运算结果。 Status Check(E)Status Check(E) 初始条件：表达式 E 存在； 操作结果： 检查表达式 E 是否还存在没有赋值的变量， 以便求算数表达式E 的值。 long Value(E)long Value(E) 初始条件：表达式 E 存在； 操作结果：对算术表达式求值，返回求到的结果。 void CompoundExpr(P,void CompoundExpr(P,
6、 printf(“n*“); printf(“n 1 输入正确的前缀表达式“); printf(“n 2 带括弧的中缀表示式输出“); printf(“n 3 对变量进行赋值“); printf(“n 4 对算数表达式求值“); printf(“n 5 构造一个新的复合表达式“); printf(“n 6 以表达式的原书写形式输入“); 数据结构课程设计报告数据结构课程设计报告 第第 5 页页 共共 34 页页 printf(“n 7 合并表达式中所有常数运算“); printf(“n 0 退出“); printf(“n*“); printf(“n 请输入你的选择“); choice=getche(); return choice; 在主函数中，采用多分支程序设计语句 switch()使程序产生不同的
