1162 Postfix Expression – PAT甲级真题

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.

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

题目大意：给一个语法树，输出相应的后缀表达式，用括号反映运算符的优先级。输出样例：第一行给一个正整数N，表示语法树结点的总数量。然后是N行，每行给出一个结点的信息（第i行对应第i个结点），格式为data left_child right_child，其中data是不超过10个字符的字符串，left_child和right_child分别是该结点的左右子结点的下标。结点的下标从1到N。NULL用-1表示。输出样例：对于每种情况，在一行中输出后缀表达式，括号反映运算符的优先级。任何符号之间没有多余的空格。

分析：lc中存储左孩子下标，rc中存储右孩子下标，mark用来标记一个结点是否是别人的结点，以便判断出谁是树的根结点。本题比较简单，在找到根结点后，从根结点开始进行搜索，首先输出一个 ‘(‘ 如果当前结点同时存在左右孩子，那么就分别继续搜索左右孩子，接下来输出当前结点的内容，如果只有右子树（语法树不会存在只有左子树没有右子树的情况），那么就在输出当前结点内容后进入右孩子结点继续搜索，最后输出一个 ‘)’ ~ 

#include 
using namespace std;
int n, root = 1, lc[32], rc[32], mark[32];
string Data[32];
void deal(int x) {
    cout << '('; 
    if (lc[x] * rc[x] > 1) {
        deal(lc[x]);
        deal(rc[x]);
    }
    cout << Data[x];
    if (lc[x] * rc[x] < 0) deal(rc[x]);
    cout << ')';
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> Data[i] >> lc[i] >> rc[i];
        mark[lc[i]] = mark[rc[i]] = 1;
    }
    while(mark[root]) root++;
    deal(root);
    return 0;
}