Pat class a 1162 postfix expression

1162 Postfix Expression (25 branch )

Given a syntax tree (binary), you are supposed to output the corresponding postfix expression, with parentheses reflecting the precedences of the operators.

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 20) which is the total number of nodes in the syntax tree. Then N lines follow, each gives the information of a node (the i-th line corresponds to the i-th node) in the format:

data left_child right_child

where data is a string of no more than 10 characters, left_child and right_child are the indices of this node’s left and right children, respectively. The nodes are indexed from 1 to N. The NULL link is represented by −1. The figures 1 and 2 correspond to the samples 1 and 2, respectively.

Output Specification:
For each case, print in a line the postfix expression, with parentheses reflecting the precedences of the operators.There must be no space between any symbols.

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)%))+)

Thought analysis ： This topic and 1130 similar , Are given an expression tree to find his expression , This topic requires finding the suffix expression , Then the idea is very clear , We just need to build a tree , Then it is OK to print after traversal , But pay attention to , If there is a node without a left child , Then we have to print the root node first , Here we use a st Array tags are ok . One last word , Input methods like this , We use two-dimensional arrays tree[N][2] Building trees can be more convenient , The second is to store the location of the two children , Use another w[N] Stored value

#include<bits/stdc++.h>
using namespace std;
const int N = 25;
int tree[N][2];
string w[N],value;
bool st[N];
int n,l,r,root;
void print(int t)
{
    
    if(!st[t]) cout<<w[t];
    st[t] = 1;
}
void dfs(int t)
{
    
    if (t == -1) return ;
    printf("(");
    if(tree[t][0] == -1) print(t);
    dfs(tree[t][0]);
    dfs(tree[t][1]);
    print(t);
    printf(")");
}
int main()
{
    
    cin >> n;
    for (int i = 1 ;i <= n ; i ++ )
    {
    
        cin >> value >> l >> r;
        tree[i][0] = l,tree[i][1] = r;
        st[l] = 1,st[r] = 1;
        w[i] = value;
     }
    for (int i = 1; i <= n; i ++ ) if(!st[i]) root = i;
    memset(st,0,sizeof st);
    dfs(root);
    return 0;
}

There is probably so much content , I hope I can help you .