一、  需求分析

一个表达式和一棵树之间存在自然的对应关系，实现以下操作： 

（1）以字符序列的形式输入语法正确的后缀表达式并构造表达式。 

（2）可实现对应原表达式的加、减、乘、除四则混合运算。  

    （3）运算数可以是整数、实数或变量，若是变量，可对变量赋值，以求得对应原表达式的值。

  （4）可以求表达式的中缀和后缀序列，还可以求所建立的二叉树的深度。

【测试数据】 

1)分别输入0；a; -91; 2 4 +; 1.5 a uuu / *; 2  11 + 3 ^并输出。

2)每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。 

3)还有很多测试的数据，详细请读者自行测试。

二、  概要设计

1.      抽象数据类型Expression的定义如下：

ADT Expression

{

数据对象D：D是具有数值的常量C和没有数值的变量V；

数据关系：R={<(V或者C)P(V或者C)>|V,C∈D, <(V或者C)P(V或者C)>表示                    由运算符P结合起来的表达式E} 

基本操作：

void  Input(SqStack &S, BiTree &T)

       初始条件：S, T 存在

       操作结果：输入函数，用来创建二叉树的核心函数

Status  Judge(SqStack &S){

       初始条件：S存在。

       操作结果：判断输入的表达式是否为正确的后缀表达式

LinkQueue  HierarchyBiTree(BiTree Root)

       初始条件：T 存在

       操作结果：层次遍历二叉树，把结果保存在LinkQueue

void  Print(LinkQueue Q, BiTree T)                 

       初始条件：Q为进行层次遍历得到的队列

       操作结果：层次遍历打印。

void Perorder(BiTree t)

       初始条件：树T存在。

       操作结果：前序遍历

void Inorder(BiTree t)

       初始条件：树T存在。

       操作结果：中序遍历。

void Assign(BiTree T, char V, int c, int *flag)    

       初始条件：树T存在，v为要赋值的变量，c为赋的值，flag为标志位

       操作结果：对表达式中的所有变量V的赋值c，参数flag为表示是否赋值过                      的标志  

Status Caculate(BiTree T, SqStack &S)

       初始条件：S, T存在

       操作结果：后序遍历，利用栈对表达式进行运算,最后结果以结点的形式存放                            在栈中

int   Depth(BiTree T)

       初始条件：树T存在。

操作结果：求深度

}ADT Expression

2.      主程序

void main()

{                             //伪代码

       Designer();

       while(1){

        Menu();

        scanf(" %c", &n);                               

        if(n == ‘0‘)                                  

            break;                                      

        else if(‘1‘<=n && n<=‘6‘){                        //1 ~ 6之间

            switch(n){            

                case ‘1‘:

                      Input(S, T);

                case ‘2‘:

                                          Q = HierarchyBiTree(T);                                                                                             Print(Q, T);                                            

                case ‘3‘:

                                          Perorder(T);

                     Inorder(T);

                case ‘4‘:

                                          Assign(T, ch, n, &Assign_tag); 

                case ‘5‘:

                                          Caculate(T, S1) ;

                case ‘6‘:

                     int d = Depth(T);

              default: break;

       }

    printf("\t\t\t已安全退出，感谢使用！\n");                               

}

3.      本程序包含的模块及其调用关系图

三、  详细设计

队列、栈和二叉树的类型

#define TRUE 1  

#define FALSE 0  

#define OK 1  

#define ERROR 0   

#define INFEASIBLE -1

typedef int Status;

//二叉树节点类型  

typedef enum { INT, DOU, CHAR, OPER} ElemTag; //INT为整型，DOU为实型，CHAR为字符型 ，OPER为操作符 

//二叉树数据域    

typedef struct TElemTag  { 

    ElemTag tag;   

    union 

    {    

               int n;                                  // INT

        double num;                            // DOU

        char c;                               //CHAR 和 OPER

    }; 

} TElemTag; 

//二叉树链式存储结构   

typedef struct BiTNode  { 

    TElemTag data; //数据域   

    struct BiTNode *lchild, *rchild;    //左右孩子指针   

} BiTNode, *BiTree; 

typedef BiTree SElemType;   //栈SqStack的元素    

//栈的顺序存储结构   

#define STACK_INIT_SIZE 30  //初始存储空间   

#define STACKINCREMENT 5    //存储空间增量      

typedef struct SqStack  { 

    SElemType *base; 

    SElemType *top; 

    int stacksize; 

} SqStack; 

typedef BiTree QElemType;    //队列LinkQueue的元素

typedef struct QNode {

    QElemType      data;

    struct QNode * next;

} QNode,*QueuePtr;

typedef struct {

    QueuePtr       front;

    QueuePtr       rear;

} LinkQueue;