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 7a -1 -1* 4 1+ 2 5b -1 -1d -1 -1- -1 6c -1 -1

Sample Output 1:

(((a)(b)+)((c)(-(d))*)*)

Sample Input 2:

82.35 -1 -1* 6 1- -1 4% 7 8+ 2 3a -1 -1str -1 -1871 -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;}