【题解】表达式

题意

给你一个中缀表达式即一般的算数表达式，输出前缀和后缀表达式，中缀表达式只由小写字母，构成。

题解

我们可以考虑利用中缀表达式来建立一个表达式树，考虑表达式树中，操作符是作为父节点然后变量是作为儿子节点的。那么然后建立一个表达式树呢。这实际上和优先级有关，，我们可以每次找最后一个运算的操作符将其作为当前表达式树中的根，然后该表达式中的左边作为左子树，右边作为右子树。若优先级同级，最右边的作为根。然后这样递归来建立一棵表达式树，建立完之后跑一遍先序和后序就可以得到前缀表达式和后序表达式了。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000;
int lch[maxn], rch[maxn]; char op[maxn];
int nc = 0;
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;
}
char str[1005];
void preorder(int x)
{
    if(x)
    {
        printf("%c",op[x]);
        preorder(lch[x]);
        preorder(rch[x]);
    }
}
void postorder(int x)
{
    if(x)
    {
        postorder(lch[x]);
        postorder(rch[x]);
        printf("%c",op[x]);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",str);
        nc=0;
        build_tree(str,0,strlen(str));
        preorder(1);
        printf("\n");
        postorder(1);
        printf("\n");
    }
    return 0;
}