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

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

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


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<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);
}