1162 Postfix Expression

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.

Figure 1	Figure 2

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

The main idea of the topic  

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

Be careful

Three situations ：

① When there are no left or right children , Access the current node directly

② When both left and right children exist Do a postorder traversal namely ： Left -> Right -> root

③ When the left child does not exist and the right child exists , Perform a preorder traversal, that is ： root -> Right  

AC Code

/*
* @Author: Spare Lin
* @Project: AcWing2022
* @Date: 2022/6/28 14:28
* @Description: PAT (Advanced Level) 1162 Postfix Expression
*/

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 25;

typedef struct {
    int l, r;   // Left and right children 
    string v;   // A weight 
} Node;

Node node[MAXN];
int n, root, flag[MAXN];

void dfs(int index) {
    cout << '(';
    // Neither left nor right children exist   Directly output node weights 
    if (node[index].l == -1 && node[index].r == -1) {
        cout << node[index].v;
    }
    // There are both left and right children   Then perform post order traversal 
    else if (node[index].l != -1 && node[index].r != -1) {
        dfs(node[index].l);
        dfs(node[index].r);
        cout << node[index].v;
    }
    // In the example - As a minus sign   Perform a preorder traversal   That is, the left child does not exist   Right child exists   First access the node weights and then access the right child 
    else {
        cout << node[index].v;
        dfs(node[index].r);
    }
    cout << ')';
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> node[i].v >> node[i].l >> node[i].r;
        if (node[i].l != -1) flag[node[i].l] = 1;  // Whether the left child of the current node exists 
        if (node[i].r != -1) flag[node[i].r] = 1;  // Whether the right child of the current node exists 
    }
    // Traverse to find the root node 
    for (int i = 1; i <= n; ++i) {
        if (flag[i] == 0) {
            root = i;
        }
    }

    dfs(root);

    return 0;
}