1162 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)%))+) 每个节点用一个结构体存储，结构体信息应包括结点值，左右孩子编号；
* 处理步骤先找出根节点，再应根节点进行后序遍历，但应注意：如果有
* 右孩子而没有左孩子，那么此根节点作为符号前缀，那么应该将根节点
* 先于孩子结点输出，否则先左孩子再右孩子最后根节点；
/*** 每个节点用一个结构体存储，结构体信息应包括结点值，左右孩子编号；* 处理步骤先找出根节点，再应根节点进行后序遍历，但应注意：如果有* 右孩子而没有左孩子，那么此根节点作为符号前缀，那么应该将根节点* 先于孩子结点输出，否则先左孩子再右孩子最后根节点；
*/#include <iostream>using namespace std;struct Node
{string s;int l, r;
};
const int N = 30;
bool hs[N]; //hs数组为了找出根节点
struct Node tr[N];
int n, root;void Read()
{cin >> n;for(int i=1; i<=n; ++i){string s;int l, r;cin >> s >> l >> r;if(l != -1) hs[l] = 1; if(r != -1) hs[r] = 1;tr[i] = {s, l, r};}
}void beh_traver(int root)
{if(root == -1) return; //递归边界int l = tr[root].l, r = tr[root].r;string s = tr[root].s; cout << '(';//如果有右孩子而没有左孩子，那么此根节点作为符号前缀，那么应该//将根节点先于孩子结点输出，否则先左孩子再右孩子最后根节点；if(l == -1 && r != -1) cout << s; beh_traver(l); beh_traver(r);if(l == -1 && r != -1) cout << ')';else cout << s << ')';
}int main()
{Read();for(root = 1; hs[root] != 0; ++root); //找到根节点beh_traver(root);return 0;
}
