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

分手后的思念是犯贱 2024-04-18 15:28 22阅读 0赞

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.

<table> 
 <thead> 
  <tr> 
   <th><img alt="infix1.JPG" src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzRkMWM0YTk4LTMzY2MtNDVmZi04MjBmLWM1NDg4NDU2ODFiYS5KUEc?x-oss-process=image/format,png"></th> 
   <th><img alt="infix2.JPG" src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tL2I1YTNjMzZlLTkxYWQtNDk0YS04ODUzLWI0NmUxZThiNjBjYy5KUEc?x-oss-process=image/format,png"></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Figure 1</td> 
   <td>Figure 2</td> 
  </tr> 
 </tbody> 
</table>

### 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][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;
    }

[https_www.liuchuo.net_archives_3798]: https://www.liuchuo.net/archives/3798