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

これにより、見栄えの良いツリーが得られるはずです。多くの場合、文字列が有効かどうかを確認し、必要に応じて補正/修正する必要があります。

于 2012-08-29T17:39:37.973 に答える
2

このコードは、スタックを使用して、閉じ括弧がまだ表示されていない開き括弧に対応するノードを格納します。開いた括弧を見つけると、新しいノードをスタックにプッシュします。閉じ括弧を見つけると、現在の最上位ノードをスタックから削除し、その親の子 (そのすぐ下にあったノード) にします。

#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 に答える