Решение, которое я придумал, является итеративным решением, основанным на стеке. Есть несколько правил, которым нужно следовать:
- выталкивает все, что приходит в стек
- Если вы столкнулись с
) стека, начните удалять элементы, пока не встретите (, а затем выскакиваете это тоже.
- Когда вы добавляете элементы на шаге 2, сохраняйте их в векторе, кроме
) и (.
- Создайте узел дерева и отметьте дочерние элементы родителя как все элементы вектора.
- поместите родительский узел обратно в стек.
Давайте посмотрим на вашем примере:
S = "((a($Z))(An))", для ясности изменено ' ' -> 'a'.
Примечание : стек растет вправо.
Stack["((a($Z"]
encounter ')'
Stack["((a"], vector<"Z$">
reverse vector -> vector<"$Z">
Parent Node -> N(id='1'), children -> <N(id='$'), N(id='Z')>
push N(1) to stack
Stack["((a1]
encounter ')'
Stack["("], vector<"1a">
reverse vector -> vector<"a1">
Parent Node -> N(id='2'), children -> <N(id='a'), N(id=1)>
push N(2) to stack
Stack["(2(An"]
encounter ')'
...
Вы можете продолжить это, чтобы добраться до вершины. Когда вы закончите, то есть строка исчерпана, вы получите в стеке ровно один элемент, который будет вашим родительским элементом или корнем дерева.
Код:
Node* solve(string s) {
stack<Node *> st;
int idx = 0, rt = 1;
while (idx < s.size()) {
Node *n = get_node(s[idx]);
st.push(n);
++idx;
if (st.top()->v == ')') {
st.pop();
vector<Node *> child;
while (st.size() && st.top()->v != '(') {
child.push_back(st.top()); st.pop();
}
if (st.top()->v == '(') st.pop();
Node *par = get_node('0' + rt++);
reverse(child.begin(), child.end());
for (Node *t : child) {
t->parent = par;
par->child.push_back(t);
}
st.push(par);
}
}
return st.top();
}
Полный рабочий код
Этот код является общей реализацией, поэтому любой узел может иметь столько же дочерних элементов, что и построение дерева n-arry.
например:
input: ((a($Zk))(An))
output:
Parent: 4: 2 3
Parent: 2: a 1
Parent: 3: A n
Parent: 1: $ Z k