题目:设计一个程序实现基于二叉树表示的算术表达式的操作。
一、 需求分析
1、以二叉树为基本模型,构建了表达式二叉树。 算术表达式的合法输入数据包括变量
(,a~z)、常量( 0-9)和二元运算符(+,-,*,/,^(乘幂)),一元运算符
(sin, cos,tan)。演示程序以人机对话的方式执行,即在计算机上显示提示信息后 ,
由用户在键盘上输入对应的数据或命令,程序将执行相应的操作并显示下一步信息。表
达式的输出主要是用带括号的中缀表示式输出调用函数 InorderExp( ExpTree E, Status ( *
Visit )( ExpTree e ) );
2、 程序的目的实现算术表达式在计算机里的树形存储,实现基本的运算(+,-,*,
/,^(乘幂))sin,cos,tan),求偏导,常数合并。
3、 测试数据( 附后 )。
提供两种方式的测试:一种是自动测试,即程序调用 test 文件夹 data.txt 文件里的测试
数据,另一种方式是手动测试,即按程序提示一步一步输入测试。
除了满足要求的 0; a; -91; +a*bc; +*5^x2*8x; +++*3^x3*2^x2x6,还有几十组数据测试。
每当输入一个表达式后,程序提示用户赋值,再对表达式求值。为了方便用户,我在程序
中用数组保存着一些测试数据,以供测试用。
二、概要设计
1.以字符串保存输入的字符序列。
2.提示用户赋值的同时将数据取出建立二叉树。
3.用后根遍历的次序用递归函数对表达式求值,求值时进行相应的转化,将运算数的字符
形式转换成整数形式。
4.用中缀表达式输出表达式时,适当添加括号,以正确反映运算的优先次序。
5.抽象数据类型的定义:
1)、存放表达式的结构类型,是以二叉树为基本原型。
typedef enum{ OPER, VAR, ORD }ElemTag;//运算符,变量,常量
typedef struct ExpNode
{
ElemTag tag; //标记
union{
char expr[4]; //存放运算符名
struct{
char var; //存放变量名
int val; //存放变量的值,初始值为 0
}vary; //存放变量
int ordina; //存放常量值
};
struct ExpNode *lchild, *rchild; /* 左右孩子指针 */
} *ExpTree; /* 二叉树的二叉链表存储表示 */
基本操作:
int Random( int nMin, int nMax );
评论7