Построить двоичное дерево из s-выражения в C++

Question

empty tree ::= ()
tree ::= empty tree | (w tree tree)
ex:
()
empty tree

(99(5()())(35(-5()())()))

     99
    /  \
   5   35
      /
     -5

class Node
{
public:
    int weight; // weight can be negative!
    Node *left, *right;
    Node():weight(0),left(NULL),right(NULL){}
    Node(int d):weight(d),left(NULL),right(NULL){}
};

Построить двоичное дерево по заданному условию

У меня проблема с созданием, моя программа сломается, и я понятия не имею, почему это произошло, ниже приведен мой код, и я распечатываю некоторую информацию для отладки, take (99(5()())(35(-5()())())) в качестве контрольного примера он выведет 99 (5 (и думаю, возможно, проблема в том, с чем я имею дело), ​​где я возвращаю узел, который имеет значение NULL, но я не могу найти проблема с этим. Кстати, это дерево, как ожидается, будет обрабатывать сотни узлов в каждом дереве, и каждый из тестовых случаев содержит до десяти деревьев, у меня не хватит времени с этой программой или что мне нужно делать? Спасибо за ваше время

Node* MyBinaryTreeOps::constructTree(Node *root, std::string treeStr)const
{
    int idex = 1;//always look at the treeStr[1]
    Node *cur=NULL;//use to pass in recursive call
    if(treeStr[idex]!='('&&treeStr[idex]!=')'){//meet number create new node
       stringstream ss;
       while(treeStr[idex]!='('){
             ss<<treeStr[idex];
             if(treeStr.size()>1){//if size > 1 then remove the treeStr[1],to let treeStr[1] become next char in treeStr
                treeStr.erase(1,1);
             }
        }
        int num=0;
        ss>>num;
        std::cout<<num<<std::endl;//print out just for debug
        std::cout<<treeStr[idex]<<std::endl;//print out just for debug
        root = new Node(num);
     }

    if(treeStr[idex]==')'){//meet ')' return subtree constructed
      if(treeStr.size()>1){
         treeStr.erase(1,1);
      }
       return root;
    }
    if(treeStr[idex]=='('){//meet first '(' then construct left subtree
       if(treeStr.size()>1){
          treeStr.erase(1,1);
       }

       root->left = constructTree(cur,treeStr);

    }

    if(treeStr[idex]=='('){ //meet second '(' then construct right subtree
       if(treeStr.size()>1){
          treeStr.erase(1,1);
       }
       root->right = constructTree(cur,treeStr);

    }
    if(treeStr[idex]==')'){ //meet ')' return subtree constructed
       if(treeStr.size()>1){
          treeStr.erase(1,1);
       }
       return root;
    }
}

Answer 1

Я пробовал эту проблему самостоятельно, и это функция, которую я написал.

Шаги алгоритма:

1. Найдите часть последовательности, которая представляет вес текущего узла. Преобразуйте его в int и назначьте на узел.
2. Нарезать строку, чтобы удалить вес, начальная и конечная скобка.
3. Выполните итерацию последовательности, чтобы найти точку между двумя фигурными скобками, которая разделяет дочерние узлы.
4. Разделить дочернюю строку на две последовательности (мы можем разрезать начальное дерево и использовать его как последовательность одного из дочерних узлов).
5. Если дочерний узел имеет вес (длина его последовательности больше 2), то создайте новый узел и рекурсивный алгоритм.

Кроме того, вот моя программа с некоторыми тестовыми примерами и немного расширенным классом Node:

Node* constructTree(Node* root, std::string& treeString) {
    // Find the weight of this node.
    auto weightLeft = treeString.find_first_of("(") + 1;
    auto weightRight = treeString.find_first_of("()", weightLeft);
    auto weightString = treeString.substr(weightLeft, weightRight - weightLeft);

    // Optional, we check if there is any weight, if there is not we leave zero
    // weight from constructor.
    // Works for something like that: ((1)(2)) -> (0(1)(2))
    if (weightString.length() > 0) {
        root->weight = std::stoi(weightString);
    }

    // Slice string to contain only children sequences.
    treeString.erase(0, weightRight);
    treeString.erase(treeString.length() - 1, 1);

    // Looking for index in string where a left child ends and a right child starts.
    // This point(index) is located where count of left braces and for braces
    // is the same and the counts are not zero.
    int splitPoint = -1;
    int leftBraces = 0, rightBraces = 0;
    for (int index = 0; index < treeString.length(); index++) {
        char c = treeString[index];
        if (c == '(') {
            ++leftBraces;
        }
        if (c == ')') {
            ++rightBraces;
        }

        if (leftBraces == rightBraces) {
            splitPoint = index + 1;
            break;
        }
    }

    // If split point has been found then it means that this node has children.
    if (splitPoint != -1) {
        auto leftChildString = treeString.substr(0, splitPoint);
        auto rightChildString = treeString.erase(0, splitPoint);

        // Check for length so construct will stop if there is no child.
        if (leftChildString.length() > 2) {
            root->left = new Node();
            constructTree(root->left, leftChildString);
        }

        if (rightChildString.length() > 2) {
            root->right = new Node();
            constructTree(root->right, rightChildString);
        }
    }

    return root;
}