PAT Class A 1130 Infix Expressions

Original title link

Given a syntactic binary tree, please output the corresponding infix expression, and use parentheses to reflect the precedence of operators.

Input format
The first line contains the integer N representing the number of summary points of the binary tree.

Next N lines, each giving information about a node in the following format (line i corresponds to node i):

data left_child right_child
where data is a string with a length not exceeding 10, left_child and right_child are the left and right child node numbers of the node respectively.

All nodes are numbered from 1 to N, NULL is represented by -1.

The following two figures correspond to Example 1 and Example 2, respectively.

11.JPG 222.JPG

Output format
Please output the infix expression on one line, and use parentheses to reflect the operator's precedence.

Please note that there should be no extra parentheses and no spaces between any symbols.

Data Range
1≤N≤20
Input Example 1:
8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
- -1 6
c -1 -1
Example output 1:
(a+b)*(c*(-d))
Example 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))

Solution 1:

#include using namespace std;const int N = 30;string a[N];int n, l[N], r[N], f[N];int root;void dfs(int u){if(u > n) return;if(u == -1) return;if(!((l[u] == -1 && r[u] == -1) || u == root)) cout << '(';dfs(l[u]);cout << a[u];dfs(r[u]);if(!((l[u] == -1 && r[u] == -1) || u == root)) cout << ')';}int main(){cin >> n;memset(l, -1, sizeof l);memset(r, -1, sizeof r);memset(f, -1, sizeof f);for(int i = 1; i <= n; i ++ ){cin >> a[i];cin >> l[i] >> r[i];if(l[i] != -1) f[l[i]] = i;if(r[i] != -1) f[r[i]] = i;}root = 1;while(f[root] != -1) root = f[root];dfs(root);return 0;}

Solution 2:

#include using namespace std;const int N = 30;string a[N];int n, l[N], r[N], f[N];bool is_leaf[N];int root;string dfs(int u){string left, right;if(l[u] != -1){left = dfs(l[u]);if(!is_leaf[l[u]]) left = "(" + left + ")";}if(r[u] != -1){right = dfs(r[u]);if(!is_leaf[r[u]]) right = "(" + right + ")";}return left + a[u] + right;}int main(){cin >> n;memset(l, -1, sizeof l);memset(r, -1, sizeof r);memset(f, -1, sizeof f);for(int i = 1; i <= n; i ++ ){cin >> a[i];cin >> l[i] >> r[i];if(l[i] != -1) f[l[i]] = i;if(r[i] != -1) f[r[i]] = i;if(l[i] == -1 && r[i] == -1) is_leaf[i] = true;}root = 1;while(f[root] != -1) root = f[root];cout << dfs(root);return 0;}