M24729: 括号嵌套树

dfs, stack, http://cs101.openjudge.cn/practice/24729/

思路：用栈解析括号表达式建树，再递归输出前序与后序序列。

#include <iostream>
#include <vector>
#include <stack>
#include <cctype>
using namespace std;

struct Node {
    char val;
    vector<Node*> children;
    Node(char c) : val(c) {}
};

void preorder(Node* root) {
    if (!root) return;
    cout << root->val;
    for (auto child : root->children)
        preorder(child);
}

void postorder(Node* root) {
    if (!root) return;
    for (auto child : root->children)
        postorder(child);
    cout << root->val;
}

int main() {
    string s;
    cin >> s;
    stack<Node*> st;
    Node* root = nullptr;
    Node* last = nullptr;

    for (int i = 0; i < (int)s.size(); ++i) {
        char c = s[i];
        if (isupper(c)) { 
            Node* node = new Node(c);
            if (!st.empty())
                st.top()->children.push_back(node);
            else
                root = node;
            last = node;
        } else if (c == '(') {
            st.push(last);
        } else if (c == ')') {
            st.pop();
        } else if (c == ',') {
            continue;
        }
    }

    preorder(root);
    cout << "\n";
    postorder(root);
    cout << "\n";

    return 0;
}