2019 PAT甲级秋季考试7-3 Postfix (25 分)

你的名字 2024-04-18 16:03 24阅读 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:

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.

<table> 
 <thead> 
  <tr> 
   <th><img alt="infix1.JPG" src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzRkMWM0YTk4LTMzY2MtNDVmZi04MjBmLWM1NDg4NDU2ODFiYS5KUEc?x-oss-process=image/format,png"></th> 
   <th><img alt="infix2.JPG" src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tL2I1YTNjMzZlLTkxYWQtNDk0YS04ODUzLWI0NmUxZThiNjBjYy5KUEc?x-oss-process=image/format,png"></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Figure 1</td> 
   <td>Figure 2</td> 
  </tr> 
 </tbody> 
</table>

### 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<stdio.h>
    #include<string.h>
    #include<string>
    #include<math.h>
    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    #define INF 0x3f3f3f3f
    struct node
    {
    	string val;
    	int l,r;
    }p[5000];
    void dfs(int x)
    {
    	if(p[x].l!=-1&&p[x].r!=-1)
    	{
    		printf("(");
    		if(p[x].l!=-1)dfs(p[x].l);
    		if(p[x].r!=-1)dfs(p[x].r);
    		cout<<p[x].val;
    		printf(")");
    	}
    	else
    	{
    		printf("(");
    		cout<<p[x].val;
    		if(p[x].l!=-1)dfs(p[x].l);
    		if(p[x].r!=-1)dfs(p[x].r);
    		printf(")");
    	}
    }
    int main()
    {
    	int n,i,j,root;
    	int vis[5000]={0};
    	scanf("%d",&n);
    	for(i=1;i<=n;i++)
    	{
    		cin>>p[i].val>>p[i].l>>p[i].r;
    		if(p[i].l!=-1)
    		vis[p[i].l]=1;
    		if(p[i].r!=-1)
    		vis[p[i].r]=1;
    	}
    	for(i=1;i<=n;i++)
    	{
    		if(vis[i]==0)
    		{
    			root=i;
    			break;
    		}
    	}
    	dfs(root);
    }