How to build tree from a parsed sentence in Java?

Question

I have a sentence Programcreek is a very huge and useful website. After parsing I convert it into following String format:

(TOP (S (NP (NN Programcreek)) (VP (VBZ is) (NP (DT a) (ADJP (RB very) (JJ huge) (CC and) (JJ useful)))) (. website.)))

I want to convert this parsed sentence into a tree as it appears in the diagram. How to achieve this? I'm new to Java, so I'm not aware if there is a standard way of doing it? Any help/suggestion is welcome. Thanks

Let's see if I understand this correctly - this is a string manipulation problem. Every left parenthesis other than the first should be preceded by a line break, and the number of indents equal to the current count of unclosed parentheses; and every right parenthesis other than the last should be followed by a line break, and the number of indents equal to the current count of unclosed parentheses; but when a right parenthesis is followed by a left parenthesis, we only add the line break and indents once. Is that correct? — Dawood ibn Kareem, Sep 14 '13 at 05:59
At some level, you have to decide what each of these words *mean*. Yes, we can infer that there is a proper noun, a noun, a verb, a few adjectives, a couple of adverbs, and an article or two, but Java won't know that until you tell it. You have to provide some useful kind of **mapping** to each of these things. (I'd also make the case that "website" belongs in the noun part, as well.) — Makoto, Sep 14 '13 at 05:59
Do you have the chance to change the syntax of this String? Then you could change this to XML or JSON and use one of the many and easy standard ways. — jboi, Sep 14 '13 at 06:04

score 2 · Answer 1 · answered Sep 14 '13 at 06:05

Java does not have a standard Tree structure (there are some Collection classes like TreeMap but they just use tree structures internally) so you'd have to create your own. Here's an example:

public class Node {
    public String nodeText;
    public List<Node> children = new ArrayList<Node>();
}

Now you'd have to parse your string and do something like that:

When you hit a (, you'd create a new Node and set nodeText to the text immediately following the (. Then you'd recursivly continue parsing the string and create new nodes there until you hit a ). This should end the recursion and return the list of nodes created. Where you started the recursion you'd add all returned nodes as children to your node.

That's very rudimentary and you'll have to treat the root node a bit special, but there's a lot of literature and tutorials about trees anyways.

@StephenC I know that, it's just that the algorithm I sketched does not explain how to start the recursion and to get hold of the root/top node. — Ridcully, Sep 14 '13 at 12:09

score 1 · Answer 2 · edited May 23 '17 at 11:56

1

It's worth reading more about this topic rather than asking for an answer as you have. You should at least attempt to solve the problem yourself. Some reading on trees for language http://en.m.wikipedia.org/wiki/Parse_tree

Also some info from another post on stack overflow for building trees in java Java tree data-structure?

edited May 23 '17 at 11:56

Community

1
1

answered Sep 14 '13 at 07:34

Adrian

495
2
10

How to build tree from a parsed sentence in Java?

2 Answers2