乐趣区

关于算法-数据结构:PAT甲级2019年秋季考试-73-Postfix-Expression

jiezi

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 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)%))+)

题目限度：

题目粗心：

现给定一颗语法树，要求输入其后缀表达式。

算法思路：

后缀表达式实际上就是将 a + b 的操作符移到最初变为 ab+, 然而存在非凡状况，因为 + 和 - 既能够代表加减法，又能够代表正负号，所以这里得判断 +,- 是否是和前面的数字绑定在一起作为符号位的，判断的办法就是以后的左孩子是否为空，如果为空，那么就阐明以后节点的操作符是一个符号位，和右子树的数值是一个整体。否则就是失常的先拜访左子树，后拜访右子树，最初拜访操作符。
综上所述：

  • 1、如果当期节点没有左孩子，遍历根节点，而后再遍历右子树
  • 2、如果有左孩子，进行后序遍历。

而后就是对于该数根节点的获取，应用 parent 数组保留每一个节点的根节点，初始为 0，只有输出结束后，其 parent 值仍然为 0 的，就是根节点。最初进行后序遍历输入即可。

留神点：

  • 1、因为题目说了该树是一个语法树，不存在一个操作符为二元操作符，并且还没有左孩子的状况，也就是说没有左孩子的时候就肯定是单元操作符。
  • 2、括号的输入是针对整个子树的，分三种状况，叶子节点，输入为 (节点值)，没有左孩子，输入为 (根节点，右子树)，有左孩子，输入为 (左子树，右子树，根节点)

提交后果：

AC 代码：

#include<cstdio>
#include<vector>
#include<iostream>

using namespace std;

struct Node{
    string c;
    int left,right;
}node[30];

int parent[30];

void postOrder(int root){if(root==-1) return;
    printf("(");
    if(node[root].left==-1){
        // 只有右子树，先输入以后节点，再输入右子树
        printf("%s",node[root].c.c_str());
        postOrder(node[root].right);
        printf(")");
    }else{
        // 左右子树都有，失常后序遍历即可
        postOrder(node[root].left);
        postOrder(node[root].right);
        printf("%s)",node[root].c.c_str());
    }
}

int main(){
    int N;
    scanf("%d",&N);
    Node no;
    for(int i=1;i<=N;++i){
        cin>>no.c>>no.left>>no.right;
        node[i] = no;
        parent[no.left] = i;
        parent[no.right] = i;
    }
    int root;
    for(int i=1;i<=N;++i){if(parent[i]==0){
            root = i;
            break;
        }
    }
    postOrder(root);
    return 0;
}
退出移动版