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

 

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版