PAT甲级 1130 中缀表达式

原题链接

给定一个句法二叉树，请你输出相应的中缀表达式，并利用括号反映运算符的优先级。

输入格式
第一行包含整数 N 表示二叉树的总结点个数。

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

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

所有结点编号从 1 到 N，NULL 用 -1 表示。

以下两个图分别对应样例 1 和样例 2。

11.JPG 222.JPG

输出格式
请在一行输出中缀表达式，并利用括号反映运算符的优先级。

注意，不能有多余括号，请任何符号之间不得有空格。

数据范围
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 = 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;
}

解法二：

#include <bits/stdc++.h>
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;
}