[C++知识库]PTA甲级 1130 Infix Expression (C++)

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(\le 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.

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

Caution:

测试点 2 不过是因为没考虑就一个根节点的情况（我一开始的代码是默认到最后去掉头尾的括号，但是如果只有一个根节点的话我的代码是不会在头尾加上括号的）。

Solution:

// Talk is cheap, show me the code
// Created by Misdirection 2021-08-28 18:50:17
// All rights reserved.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

string ans = "";
vector<string> input;
vector<pair<int, int>> children;

struct Node{
    int id;
    string content;
    Node *left;
    Node *right;

    Node(int k, string s){
        id = k;
        content = s;
        left = NULL;
        right = NULL;
    }

    ~Node(){}
};

void findChildren(Node *r){
    if(r == NULL) return;

    int left = children[r -> id].first;
    int right = children[r -> id].second;

    if(left != -1) r -> left = new Node(left, input[left]);
    if(right != -1) r -> right = new Node(right, input[right]);

    findChildren(r -> left);
    findChildren(r -> right);
}

void inTraverse(Node *r){
    if(r == NULL) return;

    if(r -> left != NULL || r -> right != NULL) ans += "(";
        
    if(r -> left != NULL) inTraverse(r -> left);
    ans += r -> content;
    if(r -> right != NULL) inTraverse(r -> right);

    if(r -> left != NULL || r -> right != NULL) ans += ")";
    
}

int main(){
    
    int n;
    cin >> n;
    
    input.resize(n + 1);
    children.resize(n + 1);
    unordered_map<int, bool> flags;
    
    string tmp;
    int left, right;
    for(int i = 1; i <= n; ++i){
        cin >> tmp >> left >> right;

        input[i] = tmp;
        children[i].first = left;
        children[i].second = right;
        flags[left] = flags[right] = true;
    }

    int r = 0;
    for(int i = 1; i <= n; ++i){
        if(flags[i] == false){
            r = i;
            break;
        }
    }
    
    Node *root = new Node(r, input[r]);

    findChildren(root);

    inTraverse(root);
    
    if(ans[0] == '(') printf("%s\n", ans.substr(1, ans.length() - 2).c_str());
    else printf("%s\n", ans.c_str());

    return 0;
}