BUAA计算器（表达式计算-表达式树实现）

【问题描述】

从标准输入中读入一个整数算术运算表达式，如24 / ( 1 + 2 + 36 / 6 / 2 - 2) * ( 12 / 2 / 2 )= ，计算表达式结果，并输出。

要求：
1、表达式运算符只有+、-、*、/，表达式末尾的=字符表示表达式输入结束，表达式中可能会出现空格；
2、表达式中会出现圆括号，括号可能嵌套，不会出现错误的表达式；
3、出现除号/时，以整数相除进行运算，结果仍为整数，例如：5/3结果应为1。

4、要求采用表达式树来实现表达式计算。

表达式树（expression tree）：

我们已经知道了在计算机中用后缀表达式和栈来计算中缀表达式的值。在计算机中还有一种方式是利用表达式树来计算表达式的值。表达式树是这样一种树，其根节点为操作符，非根节点为操作数，对其进行后序遍历将计算表达式的值。由后缀表达式生成表达式树的方法如下：

l 读入一个符号：

l 如果是操作数，则建立一个单节点树并将指向他的指针推入栈中；

l 如果是运算符，就从栈中弹出指向两棵树T1和T2的指针（T1先弹出）并形成一棵新树，树根为该运算符，它的左、右子树分别指向T2和T1，然后将新树的指针压入栈中。

例如输入的后缀表达为：

ab+cde+**

则生成的表达式树为：

【输入形式】

从键盘输入一个以=结尾的整数算术运算表达式。操作符和操作数之间可以有空格分隔。

【输出形式】

首先在屏幕上输出表达式树根、左子节点及右子节点上的运算符或操作数，中间由一个空格分隔，最后有一个回车（如果无某节点，则该项不输出）。然后输出表达式计算结果。
【样例输入】

24 / ( 1 + 2 + 36 / 6 / 2 - 2) * ( 12 / 2 / 2 ) =

【样例输出】

*/ /

18

【样例说明】

按照运算符及括号优先级依次计算表达式的值。在生成的表达树中，*是根节点的运算符，/ 是根节点的左子节点上运算符，/是根节点的右子节点上运算符，按题目要求要输出。

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct numop
{
     // define elemnet
    int num;
    char op;
} sto[501];

struct opstack
{
     // define stack
    int top;
    struct numop sto[500];
};

struct Tree
{
     // define Tree
    int n;
    char o;
    struct Tree *l;
    struct Tree *r;
};

struct tree_pro
{
     // tree stack
    struct Tree tree[502];
    int top;
} t;

typedef struct opstack stack;
stack o;                // operation
struct Tree *u, *v, *w; // temporary struct
char c;
int i, j, k, n;

void initstack(stack *s)
{
     // init stack
    s->top = -1;
}

void push_tree(struct tree_pro *t, int m,
               char c)
{
     // stack in member and operation
    if (m != -1)
    {
    
        t->tree[++t->top].l = NULL;
        t->tree[t->top].r = NULL;
        t->tree[t->top].n = m;
        t->tree[t->top].o = 0;
    }
    else
    {
    
        u = (struct Tree *)malloc(sizeof(struct Tree));
        v = (struct Tree *)malloc(sizeof(struct Tree));
        w = (struct Tree *)malloc(sizeof(struct Tree));
        memcpy(v, &t->tree[t->top--], sizeof(struct Tree));
        memcpy(u, &t->tree[t->top], sizeof(struct Tree));
        w->o = c;
        switch (c)
        {
    
        case '+':
            w->n = u->n + v->n;
            break;
        case '-':
            w->n = u->n - v->n;
            break;
        case '*':
            w->n = u->n * v->n;
            break;
        case '/':
            w->n = u->n / v->n;
            break;
        }
        w->l = (struct Tree *)&u;
        w->r = (struct Tree *)&v;
        memcpy(&t->tree[t->top], w, sizeof(struct Tree));
    }
}

void pushstack_o(stack *o, struct tree_pro *t, int m,
                 char c)
{
     // stack in member and operation
    if (m <= o->sto[o->top].num && o->sto[o->top].num != 3)
    {
    
        for (; o->sto[o->top].num != 3;)
        {
    
            if (m > o->sto[o->top].num)
                break;
            push_tree(t, -1, o->sto[o->top].op);
            o->top--;
            if (o->top == -1)
                break;
        }
    }
    if (m == 4)
    {
     // right round
        for (; o->sto[o->top].num != 3; o->top--)
        {
    
            push_tree(t, -1, o->sto[o->top].op);
        }
        o->top--;
    }
    else
    {
    
        o->sto[++o->top].num = m; // save number and operation
        o->sto[o->top].op = c;
    }
}

void print_tree(struct tree_pro *t)
{
    
    if (t->tree[t->top].o != 0)
        printf("%c ", t->tree[t->top].o);
    else
        printf("%d ", t->tree[t->top].n);
    if (u->o != 0)
        printf("%c ", u->o);
    else
        printf("%d ", u->n);
    if (v->o != 0)
        printf("%c \n", v->o);
    else
        printf("%d \n", v->n);
    printf("%d", t->tree[t->top].n);
}

int main()
{
    
    initstack(&o); // init all, num, operation
    t.top = -1;
    while ((c = getchar()) != '=')
    {
    
        if (c >= '0' && c <= '9')
        {
    
            for (i = 0; c >= '0' && c <= '9'; c = getchar()) // number produce
                n = c - '0' + n * 10;
            ungetc(c, stdin);
            push_tree(&t, n, 0); // stack in
            n = 0;
        }
        else if (c != ' ')
        {
    
            switch (c)
            {
     // distribute number
            case '+':
                pushstack_o(&o, &t, 1, c);
                break;
            case '-':
                pushstack_o(&o, &t, 1, c);
                break;
            case '*':
                pushstack_o(&o, &t, 2, c);
                break;
            case '/':
                pushstack_o(&o, &t, 2, c);
                break;
            case '(':
                pushstack_o(&o, &t, 3, c);
                break;
            case ')':
                pushstack_o(&o, &t, 4, c);
                break;
            }
        }
    }
    for (; o.top != -1; o.top--)
    {
    
        push_tree(&t, -1, o.sto[o.top].op);
    }
    print_tree(&t);
    return 0;
}

BUAAer？