A1130.md

A1130 Infix Expression

1.题意理解

给出一个中缀表达式树，输出对应的中缀表达式。

此题也是2017年408的一道大题。PAT在2019年还考查了相似的后缀表达式题目。

2.思路分析

中序遍历，递归输出，注意括号细节。

3.参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 32;
int have[N + 1] = {0};
int n;
struct node
{
    string data;
    int lchild, rchild;
};
vector<node> tree(N);

string inOrder(int root)
{
    //both empty
    if (tree[root].lchild == -1 && tree[root].rchild == -1)
        return tree[root].data;
    //only left empty
    if (tree[root].lchild == -1 && tree[root].rchild != -1)
        return "(" + tree[root].data + inOrder(tree[root].rchild) + ")";
    //both not empty
    if (tree[root].lchild != -1 && tree[root].rchild != -1)
        return "(" + inOrder(tree[root].lchild) + tree[root].data + inOrder(tree[root].rchild) + ")";
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        cin >> tree[i].data >> tree[i].lchild >> tree[i].rchild;
        if (tree[i].lchild != -1)
            have[tree[i].lchild] = 1;
        if (tree[i].rchild != -1)
            have[tree[i].rchild] = 1;
    }

    int root = 1;
    while (have[root])
        root++;
    string ans = inOrder(root);
    if (ans[0] == '(')
        ans = ans.substr(1, ans.size() - 2);
    cout << ans << endl;
    // system("pause");
    return 0;
}