[PAT-A] 1130 Infix Expression

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        int n = Integer.parseInt(inputs[0]);

        int[] l = new int[30];
        int[] r = new int[30];
        String[] w = new String[30];
        boolean[] hasFather = new boolean[30];
        Arrays.fill(l, -1);
        Arrays.fill(r, -1);
        Arrays.fill(hasFather, false);

        for (int i = 1; i <= n; i++) {
            String[] data = br.readLine().split(" ");
            w[i] = data[0];
            int lChild = Integer.parseInt(data[1]);
            int rChild = Integer.parseInt(data[2]);

            if (lChild != -1) {
                l[i] = lChild;
                hasFather[lChild] = true;
            }
            if (rChild != -1) {
                r[i] = rChild;
                hasFather[rChild] = true;
            }
        }

        int root = 1;
        while (hasFather[root]) {
            root++;
        }

        StringBuilder res = new StringBuilder();
        dfs(root, l, r, w, res);

        if (res.length() > 0 && res.charAt(0) == '(') {
            res.deleteCharAt(0);
        }
        if (res.length() > 0 && res.charAt(res.length() - 1) == ')') {
            res.deleteCharAt(res.length() - 1);
        }

        System.out.println(res);
    }

    private static void dfs(int u, int[] l, int[] r, String[] w, StringBuilder res) {
        if (u != -1) {
            int cnt = 0;
            if (l[u] != -1) {
                cnt++;
            }
            if (r[u] != -1) {
                cnt++;
            }

            if (cnt > 0) {
                res.append("(");
            }
            dfs(l[u], l, r, w, res);

            res.append(w[u]);

            dfs(r[u], l, r, w, res);
            if (cnt > 0) {
                res.append(")");
            }
        }
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30;

int n;
int l[N], r[N];
string w[N], res;
bool has_fa[N];

void dfs(int u) {
    if (u != -1) {
        int cnt = 0;
        if (l[u] != -1) cnt++;
        if (r[u] != -1) cnt++;

        if (cnt) res += "(";
        dfs(l[u]);

        res += w[u];

        dfs(r[u]);
        if (cnt) res += ")";
    }
}

int main() {
    memset(l, -1, sizeof(l));
    memset(r, -1, sizeof(r));

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        string data;
        int lchild, rchild;
        cin >> data >> lchild >> rchild;
        w[i] = data;

        if (lchild != -1) {
            l[i] = lchild;
            has_fa[lchild] = true;
        }
        if (rchild != -1) {
            r[i] = rchild;
            has_fa[rchild] = true;
        }
    }

    int root = 1;
    while (has_fa[root]) root++;

    dfs(root);

    if (res[0] == '(') res = res.substr(1);
    if (res[res.size() - 1] == ')') res.pop_back();
    cout << res << endl;

    return 0;
}