SDUT2484 算术表达式的转换(表达式树)

题目链接。

分析：

转换成表达式树，然后先序、中序、后序遍历。

AC代码如下：

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

#define maxn 1000

int lch[maxn], rch[maxn], nc = 0;
char op[maxn];

int build_tree(char *s, int x, int y) {
    int i, c1 = -1, c2 = -1, p = 0;
    int u;

    if(y-x == 1) {
        u = ++nc;
        lch[u] = rch[u] = 0; op[u] = s[x];
        return u;
    }

    for(i=x; i<y; i++) {
        switch(s[i]) {
        case '(': p++; break;
        case ')': p--; break;
        case '+': case '-': if(!p) c1 = i; break;
        case '*': case '/': if(!p) c2 = i; break;
        }
    }

    if(c1 < 0) c1 = c2;
    if(c1 < 0) return build_tree(s, x+1, y-1);

    u = ++nc;
    lch[u] = build_tree(s, x, c1);
    rch[u] = build_tree(s, c1+1, y);
    op[u] = s[c1];

    return u;
}

void pre_print(int u) {
    if(u != 0) {
        printf("%c", op[u]);
        pre_print(lch[u]);
        pre_print(rch[u]);
    }
}

void in_print(int u) {
    if(u != 0) {
        in_print(lch[u]);
        printf("%c", op[u]);
        in_print(rch[u]);
    }
}

void las_print(int u) {
    if(u != 0) {
        las_print(lch[u]);
        las_print(rch[u]);
        printf("%c", op[u]);
    }
}


int main() {
    char s[5000];
    while(scanf("%s", s) == 1) {

        build_tree(s, 0, strlen(s)-1);

        pre_print(1);
        putchar('
');

        in_print(1);
        putchar('
');

        las_print(1);
        putchar('
');
    }

    return 0;
}