4274. 后缀表达式

给定一个二叉表达式树，请你输出相应的后缀表达式，要求使用括号反映运算符的优先级。

输入格式

第一行包含整数 N，表示节点数量。节点编号 1∼N。

接下来 N 行，每行给出一个节点的信息（第 i 行对应第 i 个节点），格式为：

data left_child right_child

其中，data 是一个不超过 10 个字符的字符串，left_child 和 right_child 分别是该节点的左右子节点的编号。

没有子节点（即 NULL），则用 −1 表示。

下面两图分别对应给出的两个样例。

输出格式

在一行中输出答案，表达式符号之间不得有空格。

数据范围

1≤N≤20

输入样例1：

8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
- -1 6
c -1 -1

输出样例1：

(((a)(b)+)((c)(-(d))*)*)

输入样例2：

8
2.35 -1 -1
* 6 1
- -1 4
% 7 8
+ 2 3
a -1 -1
str -1 -1
871 -1 -1

输出样例2：

(((a)(2.35)*)(-((str)(871)%))+)

代码：

// 树求后缀表达式
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
string v[N];
int l[N], r[N];
bool st[N];
int root;
void dfs(int u)
{
    cout << '(';

    if (l[u] != -1 && r[u] != -1) //当前为运算符
    {
        dfs(l[u]);
        dfs(r[u]);
        cout << v[u];
    }
    else if (l[u] == -1 && r[u] == -1) // 当前为数值
    {
        cout << v[u];
    }
    else // 只有右子树 当前为负号
    {
        cout << v[u];
        dfs(r[u]);
    }

    cout << ')';
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i] >> l[i] >> r[i];
        if (l[i] != -1)
            st[l[i]] = 1;
        if (r[i] != -1)
            st[r[i]] = 1;
    }

    for (int i = 1; i <= n; i++)
        if (!st[i])
            root = i;

    dfs(root);

    return 0;
}