PAT2019秋7-3 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 1Figure 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.

思路

这是一道树的遍历+字符串处理的题，解答与1130相似，区别是不用去除外层的括号。

代码

#include<stdio.h> #include<string.h> #include<iostream> using namespace std; struct node{ string data; int lchild,rchild; }a[25]; string dfs(int x){ if(a[x].lchild==-1&&a[x].rchild==-1) return "("+a[x].data+")"; else if(a[x].lchild==-1&&a[x].rchild!=-1) return "("+a[x].data+dfs(a[x].rchild)+")"; else if(a[x].lchild!=-1&&a[x].rchild!=-1) return "("+dfs(a[x].lchild)+dfs(a[x].rchild)+a[x].data+")"; } int main(){ int n,have[25]; memset(have,0,sizeof(have)); scanf("%d",&n); for(int i=1;i<=n;i++){ cin>>a[i].data>>a[i].lchild>>a[i].rchild; have[a[i].lchild]=1; have[a[i].rchild]=1; } int root=1; while(have[root]) root++; string str=dfs(root); cout<<str; return 0; }