CODEWITHSUNDEEP
c++algorithmtree
YAKOVM
YAKOVM

Reputation: 10153

Build a tree for string of parentheses

I have a 

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

Given a string char* str which consits of sequence of (,) I need to build a tree,for this string ,for example : for string (()())() the following tree will be built:

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

Upvotes: 1

Views: 4136

Answers (3)

Ambroz Bizjak
Ambroz Bizjak

Reputation: 8115

This code uses a stack to store nodes corresponding to open parens for which a close paren has not yet been seen. When it sees an open paren, it pushes a new node to the stack. When it sees a close paren, it removes the current top node from the stack, and makes it a child of its parent, which is the node that was just below it.

#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;
}

This uses std::list to store sibling nodes, which is easier to work with than what you have proposed. However the same algorithm should work there too.

Upvotes: 2

maximus ツ
maximus ツ

Reputation: 8065

You can use stack to implement this, once you find left parenthesis,then add this node to stack. if again left parenthesis add child to top most element of stack. on right parenthesis remove node from stack. that's it.

Upvotes: 0

Samy Arous
Samy Arous

Reputation: 6812

Your tree is a little hard to read. I'm assuming that each parenthesis is a node and all nested parenthesis are child nodes.

Here's a simple algorithm:

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

This should give you a good looking tree. Ofc you have to check if the string is valid, and compensate/correct when needed.

Upvotes: 2

Related Questions