【PAT甲级 - C++题解】1130 Infix Expression

1130 Infix Expression

Given a syntax tree (binary), you are supposed to output the corresponding infix 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 infix expression, with parentheses reflecting the precedences of the operators. Note that there must be no extra parentheses for the final expression, as is shown by the samples. 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))
• 1

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

题意

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

思路

用数组 l 和 r 分别记录每个结点的左右孩子编号，另外要用 st 来记录该结点是否是根结点，以及用 is_leaf 来记录该结点是否是叶子结点。

模拟二叉树的中序遍历，先遍历左子树再遍历右子树。在遍历左右子树的过程中，去判断左右孩子是否是叶子结点，因为题目对括号没有严格的限制，只要左右孩子不是叶子结点，那么左右子树得到的字符串前后就需要用括号包起来。

输出最终结果。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 30;
string w[N];
int l[N], r[N];
bool st[N], is_leaf[N];
int n;
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 + w[u] + right;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i] >> l[i] >> r[i];
        //标记该结点不是根结点
        if (l[i] != -1)    st[l[i]] = true;
        if (r[i] != -1)    st[r[i]] = true;
        if (l[i] == -1 && r[i] == -1)  is_leaf[i] = true;    //记录该结点是叶节点
    }
    int root = 1;
    while (st[root]) root++; //找到根结点
    cout << dfs(root) << endl;
    return 0;
}