PAT（甲级）2019年秋季考试 7-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.
译：每个输入文件包含一个测试用例，对于每种情况，第一行包含一个表示语法树中结点总数的整数 N (≤20) 。 接下来 N 行，每行用如下格式给定一个结点的信息(第 i 行 表示第 i 个结点)：
data left_child right_child
data 是一个不超过 10 个字母的字符串， left_child 和right_child是左右孩子结点的索引。结点从 1 到 N 编号。空链 NULL 用 -1 表示。
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 Input1 (样例输入1):
8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
- -1 6
c -1 -1
Sample Output1 (样例输出1):
(((a)(b)+)((c)(-(d))*)*)
Sample Input2 (样例输入2):
8
2.35 -1 -1
* 6 1
- -1 4
% 7 8
+ 2 3
a -1 -1
str -1 -1
871 -1 -1
Sample Output2 (样例输出2):
(((a)(2.35)*)(-((str)(871)%))+)
The Idea：
乍一看好像就是一个后序遍历，后缀表达式的求解。
但是当你写好后缀表达式之后，你会发现，得到的答案与给出的两个样例都有差别。
仔细研究样例，可发现，样例中的 - 作为负号 时，其访问顺序并不是后缀，而是一种中缀，当其不是算符的时候，会满足左子树为空，此时的正确的语法表达为 先访问根节点，再访问右子树。
其他时候都是先访问左子树，再访问右子树，再访问根节点。
The Codes:
#include<bits/stdc++.h>
using namespace std ;
struct node{
string val ;
int left = -1 , right = -1 ;
}tree[22] ;
int n , fa[22] ;
string ans ;
string dfs(int root){
if(root == -1) return "" ; // 空节点
// 叶子结点，直接返回字符串： "(tree[root].val)"
if(tree[root].left == -1 && tree[root].right == -1) return "(" +tree[root].val+ ")";
string s = "(" ;
if(tree[root].left == -1 && tree[root].right != -1){ // 左子树为空，右子树非空
s += tree[root].val ;
s += dfs(tree[root].right) ;
}else{
s += dfs(tree[root].left) ;
s += dfs(tree[root].right) ;
s += tree[root].val ;
}
s += ")" ;
return s ;
}
int main(){
for(int i = 1 ; i < 22 ; i ++) fa[i] = i ; // 初始化
scanf("%d" , &n) ;
int l , r ;
for(int i = 1 ; i <= n ; i ++){
cin >> tree[i].val >> l >> r ;
if(l != -1) {
fa[l] = i ;
tree[i].left = l ;
}
if(r != -1) {
fa[r] = i ;
tree[i].right = r ;
}
}
int root ;
for(int i = 1 ; i <= n ; i ++) // 找出树的根节点的编号
if(fa[i] == i) {
root = i ;
break ;
}
string ans = dfs(root) ;
cout << ans << endl ;
return 0 ;
}