4274. Suffix expression

Given a binary expression tree , Please output the corresponding suffix expression , Brackets are required to reflect the priority of the operator .

Input format

The first line contains integers N, Represents the number of nodes . Node number 1∼N.

Next N That's ok , Each row gives information about a node （ The first i Row corresponds to the second row i Nodes ）, The format is ：

data left_child right_child

among ,data It's not more than 10 Character string ,left_child and right_child Are the numbers of the left and right child nodes of the node .

No child node （ namely NULL）, Then use −1 Express .

The following two figures correspond to the two examples given .

Output format

Output answers in one line , There must be no spaces between expression symbols .

Data range

1≤N≤20

sample input 1：

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

sample output 1：

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

sample input 2：

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

sample output 2：

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

Code ：

//  Tree suffix expression 
#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) // Currently operator 
    {
        dfs(l[u]);
        dfs(r[u]);
        cout << v[u];
    }
    else if (l[u] == -1 && r[u] == -1) //  Current value 
    {
        cout << v[u];
    }
    else //  Only the right subtree   Currently negative 
    {
        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;
}