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

分手后的思念是犯贱 2024-04-18 15:28 140阅读 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:

  1. 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.














infix1.JPG infix2.JPG
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:

  1. 8
  2. * 8 7
  3. a -1 -1
  4. * 4 1
  5. + 2 5
  6. b -1 -1
  7. d -1 -1
  8. - -1 6
  9. c -1 -1

Sample Output 1:

  1. (((a)(b)+)((c)(-(d))*)*)

Sample Input 2:

  1. 8
  2. 2.35 -1 -1
  3. * 6 1
  4. - -1 4
  5. % 7 8
  6. + 2 3
  7. a -1 -1
  8. str -1 -1
  9. 871 -1 -1

Sample Output 2:

  1. (((a)(2.35)*)(-((str)(871)%))+)

题目分析

这道题属于树和DFS的类型。不过里面暗含玄机:
1.因为题目给的是左右孩子的编号,建树用的是向量和结构体,用孩子的编号直接访问孩子节点。
2.DFS只是一种思想,如何编写DFS函数需要根据题目的特点来决定,本题的DFS函数写法跟1130(中缀表达式)类似,可参考liuchuo的1130题解:https://www.liuchuo.net/archives/3798

满分代码

  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4. struct node{
  5. string data;
  6. int l,r;
  7. };
  8. vector<node> v;
  9. string f(int x){
  10. if(v[x].l==-1 && v[x].r==-1){
  11. return "("+v[x].data+")";
  12. }
  13. if(v[x].l==-1 && v[x].r!=-1){
  14. return "("+v[x].data+f(v[x].r)+")";
  15. }
  16. return "("+f(v[x].l)+f(v[x].r)+v[x].data+")";
  17. }
  18. int main(){
  19. int n;
  20. scanf("%d\n",&n);
  21. v.resize(n+1);
  22. vector<int> a(n+1);
  23. a.clear();
  24. for(int i=1;i<=n;i++){
  25. cin>>v[i].data>>v[i].l>>v[i].r;
  26. if(v[i].l!=-1)a[v[i].l]=1;
  27. if(v[i].r!=-1)a[v[i].r]=1;
  28. }
  29. for(int i=1;i<=n;i++){
  30. if(a[i]==0){
  31. cout<<f(i);
  32. break;
  33. }
  34. }
  35. return 0;
  36. }

发表评论

表情:
评论列表 (有 0 条评论,140人围观)

还没有评论,来说两句吧...

相关阅读