题 目：
算术表达式与二叉树
学生姓名
学 号：
学 院：
年 月 日
目 录
1 需求分析 ..........................................................1
1.1 需要达到的目标..............................................1
1.2 这个算法的要求..............................................1
2 总体设计 ..........................................................2
3 详细设计 ..........................................................3
1、数据类型的声明：.............................................3
2、表达式的抽象数据类型定义.....................................3
3、整体设计.....................................................5
4 系统实现 ..........................................................6
4.1、二叉树的存储类型...........................................6
4.2、顺序栈的存储类型...........................................6
4.3、表达式的基本操作...........................................7
4.4、主程序和其他伪码算法.......................................8
4.5、函数的调用关系............................................11
5 系统测试 .........................................................12
4.1.进入演示程序主界面.........................................12
4.2.第一次输入，需要选择 1 功能.................................12
6 结语 .............................................................16
附 源代码..........................................................17
二叉树的算数表达
1
1 需求分析
1.1 需要达到的目标
一个 表达式和一棵二叉树之间，存在着自然的对应关系。我需要写一个程
序，实现基于二叉树表示的算术表达式的操作。
1.2 这个算法的要求
假设算术表达式 Expression 内可以含有变量(a~z)、常量(0~9)和二元运算
符(+，，*，/, ^(乘幂)。实现以下操作:
(1) ReadExpre(E)- _以字符序列的形式输入语法正确的前缀表达式并构
造表达式 E。(2) WriteExpre(E)- 用带括弧的中缀表达式输出表达式 E。
(3) Assign(V,c)-实现对变量 V 的赋值(V=c)， 变量的初值为 0。
(4) Value(E)-对算术表达式 E 求值。
(5) CompoundExpr (P, E1，E2) -_构造-一个新的复合表达式(E1) P (E2)
[测试数据]
(1)分别输入 0; a; -91; +a*bc; +*5^x2*8x; +++*3^x3*2^x2x6 并输出。
(2)每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。
二叉树的算数表达
2
2、总体设计
一个表达式和一棵二叉树之间存在一一对应的关系。本程序主要用前缀表达
式建树，中序遍历并适当加括号实现中缀输出。具体操作即对树的程序进行处理，
再输出
二叉树的算数表达
3
3 详细设计
3.1、数据类型的声明：
在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助
存储结构
/*头文件以及存储结构*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW 0
typedef int Status;
3.2、表达式的抽象数据类型定义
ADT Expression{
数据对象 D：D 是具有数值的常量 C 和没有数值的变量 V；
数据关系：R={<(V 或者 C)P(V 或者 C)>|V,C∈D, <(V 或者 C)P(V 或者 C)>表示
由运算符 P 结合起来的表达式 E}
基本操作：
Status Input_Expr(&string,flag)
操作结果：以字符序列的形式输入语法正确的前缀表达式，保存到字符串
string； 参数 flag 表示输出的提示信息是什么，输入成功返回 OK，否则，返回
ERROR。
void judge_value(&E,&string,i)
初始条件：树 E 存在，表达式的前缀字符串 string 存在；
