PAT-A 真题 – 1130 Infix Expression

发布于 / PAT-甲级 / 0 条评论

Given a syntax tree (binary), you are supposed to output the corresponding infix 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.

infix1.JPG infix2.JPG
Figure 1 Figure 2

Output Specification:

For each case, print in a line the infix expression, with parentheses reflecting the precedences of the operators. Note that there must be no extra parentheses for the final expression, as is shown by the samples. 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))

题目大意:第一行给定数字N,接着给出N行,每行第一个是字符串,第二个是左孩子,第三个是右孩子,要求输出中序表达式(中序遍历,表达式要求加括号)

这道题千万千万不要被题目样例给的“+,-,*,/,%”给迷惑了,最后一个测试点的运算符根本就不是这些,如果你只有最后一个测试点错了,请大喊:出题人坏得很!!!!!

那么如何判断是不是运算符呢?只需要判断当前节点有没有孩子就好了,如果有孩子,一定是运算符,否则就形不成表达式了对不对~

如何判断根节点呢?找所有的输入,肯定有一个点,不是任何一个节点的孩子,这个点肯定就是根节点啦

最后,注意一下式子的最外层不要有括号,不要输出类似((a+b)*(c+d))的形式~

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

typedef struct{
  string n; 
  int lchild, rchild;
} node;
vector<node> T;

void dfs(int root, bool isRoot = true){
  if(root == -1) return;
  bool isLeaf = T[root].lchild == -1 && T[root].rchild == -1;
  if(!isRoot && !isLeaf) cout << '(';
  dfs(T[root].lchild, false);
  cout << T[root].n;
  dfs(T[root].rchild, false);
  if(!isRoot && !isLeaf) cout << ')';
}

int main(){
  int cnt, _root[25] = {0};
  cin >> cnt;
  T.resize(cnt + 1);
  for(int i = 1; i <= cnt; i++){
    cin >> T[i].n >> T[i].lchild >> T[i].rchild;
    if(T[i].lchild != -1) _root[T[i].lchild] = 1;
    if(T[i].rchild != -1) _root[T[i].rchild] = 1;
  }
  //find root
  for(int i = 1; i <= cnt; i++)
    if(_root[i] == 0){
      dfs(i);
      break;
    }
  cout << endl;
  return 0;
}

转载原创文章请注明,转载自: 斐斐のBlog » PAT-A 真题 – 1130 Infix Expression
目前还没有评论,快来抢沙发吧~