1

我有一个

typedef struct node
{
   node* br;
   node* son;
};

给定一个char* str包含 的序列的字符串(，) 我需要为该字符串构建一棵树，例如：对于字符串 (()())()，将构建以下树：

       br        br 
node ----- node ---- NULL
    |son    |son
    |      NULL
    |   br        br      br
   node --- node --- node --- NULL
           |son   |son
          NULL   NULL
4

3 回答 3

2

你的树有点难读。我假设每个括号都是一个节点，所有嵌套的括号都是子节点。

这是一个简单的算法：

We start with a root node representing the empty string.
For each char c in the string s:
    if c == '(':
        create a new child node
        move to the new created node
    else:
        move to the parent node

这应该给你一棵好看的树。Ofc 您必须检查字符串是否有效，并在需要时进行补偿/纠正。

于 2012-08-29T17:39:37.973 回答
2

此代码使用堆栈来存储与尚未看到关闭括号的打开括号相对应的节点。当它看到一个开放的括号时，它将一个新节点推入堆栈。当它看到一个 close paren 时，它会从堆栈中删除当前的顶部节点，并使其成为其父节点的子节点，父节点是其下方的节点。

#include <list>
#include <stack>
#include <functional>
#include <iostream>

struct Node {
    std::list<Node> children;
};

bool parse_parens (const char *str, Node *out)
{
    // stack of nodes for which open paren was seen but
    // close paren has not yet been seen
    std::stack<Node> stack;

    // push the virtual root node which doesn't correspond
    // to any parens
    stack.push(Node());

    for (size_t i = 0; str[i]; i++) {
        if (str[i] == '(') {
            // push new node to stack
            stack.push(Node());
        }
        else if (str[i] == ')') {
            if (stack.size() <= 1) {
                // too many close parens
                // (<=1 because root has no close paren)
                return false;
            }
            // Current top node on stack was created from the
            // open paren which corresponds to the close paren
            // we've just seen. Remove this node it from the stack.
            Node top = std::move(stack.top());
            stack.pop();
            // Make it a child of the node which was just below it.
            stack.top().children.push_back(std::move(top));
        }
        else {
            // bad character
            return false;
        }
    }

    if (stack.size() > 1) {
        // missing close parens
        return false;
    }

    // return the root node
    *out = std::move(stack.top());
    return true;
}

bool print_parens (const Node &node)
{
    for (std::list<Node>::const_iterator it = node.children.begin(); it != node.children.end(); ++it) {
        const Node &child = *it;
        std::cout << "(";
        print_parens(child);
        std::cout << ")";
    }
}

int main ()
{
    Node root;
    bool res = parse_parens("(())()(()())", &root);

    if (!res) {
        std::cout << "Error parsing!\n";
        return 1;
    }

    print_parens(root);
    std::cout << "\n";

    return 0;
}

这用于std::list存储兄弟节点，这比您建议的更容易使用。然而，同样的算法也应该在那里工作。

于 2012-08-29T18:12:03.583 回答
0

您可以使用堆栈来实现这一点，一旦找到左括号，然后将此节点添加到堆栈。如果再次左括号将子元素添加到堆栈的最顶部元素。在右括号中从堆栈中删除节点。就是这样。

于 2012-08-29T17:43:10.207 回答