2019年9月8日秋季PAT甲级题解--3 Postfix Expression (25 分) 暗含玄机

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

题目分析

这道题属于树和DFS的类型。不过里面暗含玄机：
1.因为题目给的是左右孩子的编号，建树用的是向量和结构体，用孩子的编号直接访问孩子节点。
2.DFS只是一种思想，如何编写DFS函数需要根据题目的特点来决定，本题的DFS函数写法跟1130（中缀表达式）类似，可参考liuchuo的1130题解：https://www.liuchuo.net/archives/3798

满分代码

#include<iostream>
#include<vector>
using namespace std;
struct node{
    string data;
    int l,r;
};
vector<node> v;
string f(int x){
    if(v[x].l==-1 && v[x].r==-1){
        return "("+v[x].data+")";
    }
    if(v[x].l==-1 && v[x].r!=-1){
        return "("+v[x].data+f(v[x].r)+")";
    }
    return "("+f(v[x].l)+f(v[x].r)+v[x].data+")";
}
int main(){
    int n;
    scanf("%d\n",&n);
    v.resize(n+1);
    vector<int> a(n+1);
    a.clear();
    for(int i=1;i<=n;i++){
        cin>>v[i].data>>v[i].l>>v[i].r;
        if(v[i].l!=-1)a[v[i].l]=1;
        if(v[i].r!=-1)a[v[i].r]=1;
    }
    for(int i=1;i<=n;i++){
        if(a[i]==0){
            cout<<f(i);
            break;
        }
    }
    return 0;
}