Leet Code Daily 2024-07-11 - Reverse Substrings Between Each Pair of Parentheses

enum class NodeType {
    kOpen = 0,
    kChar = 1,
    kTree = 2,
};

struct Node {

    NodeType type;
    char value;
    struct vector<Node*> children;

    void toString(string& out, bool rev = true) {
        if (this->type == NodeType::kChar) {
            out.push_back(this->value);
            return;
        }
        if (rev) {
            for (auto iter = this->children.rbegin();
                 iter != this->children.rend(); iter++) {
                (*iter)->toString(out, !rev);
            }
        } else {
            for (auto iter = this->children.begin();
                 iter != this->children.end(); iter++) {
                (*iter)->toString(out, !rev);
            }
        }
    }
};

class Solution {
public:
    string reverseParentheses(string s) {

        stack<Node*> nodes;
        for (const auto& c : "(" + s + ")") {
            switch (c) {
            case '(': {
                nodes.push(new Node{.type = NodeType::kOpen});
                break;
            }
            case ')': {
                Node* node = new Node{.type = NodeType::kTree};
                for (; nodes.top()->type != NodeType::kOpen; nodes.pop()) {
                    node->children.push_back(nodes.top());
                }
                nodes.pop();
                nodes.push(node);
                break;
            }
            default: {
                nodes.push(new Node{.type = NodeType::kChar, .value = c});
            }
            }
        }

        string ret;
        nodes.top()->toString(ret);
        return ret;
    }
};