Submission

Score: 100

User: kittipos

Problemset: composite tree

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-06 09:34:05

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int read_int(const string &s, int &i) {
    int n = 0;
    while (s[i] >= '0' && s[i] <= '9') {
        n *= 10;
        n += s[i] - '0';
        i++;
    }
    return n;
}

struct Node {
    int value;
    int left;
    int right;
    int parent;
};

vector<Node> get_tree() {    
    string inp;
    cin >> inp;

    vector<Node> nd;
    stack<pair<int, int>> st; // index and left/right
    for (int i = 0; i < inp.size(); i++) {
        if (inp[i] == '(') continue;
        if (inp[i] == ')') {st.pop(); continue;}

        Node node;
        node.value = read_int(inp, i);
        i--;
        if (!st.empty()) {
            pair<int, int> parent = st.top();
            if (parent.second == 0) {
                nd[parent.first].left = nd.size();
            } else {
                nd[parent.first].right = nd.size();
            }
            node.parent = parent.first;
        }
        node.left = -1;
        node.right = -1;

        st.push(make_pair(nd.size(), 1));
        st.push(make_pair(nd.size(), 0));
        nd.push_back(node);
    }

    return nd;
}

void sum_tree(const vector<Node> &t1, const vector<Node> &t2, int n1, int n2) {
    cout << t1[n1].value + t2[n2].value << '(';
    if (t1[n1].left != -1 && t2[n2].left != -1) {
        sum_tree(t1, t2, t1[n1].left, t2[n2].left);
    }
    cout << ")(";
    if (t1[n1].right != -1 && t2[n2].right != -1) {
        sum_tree(t1, t2, t1[n1].right, t2[n2].right);
    }
    cout << ')';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<Node> t1 = get_tree();
    vector<Node> t2 = get_tree();

    sum_tree(t1, t2, 0, 0);
    cout << '\n';


    return 0;
}