-2

i am trying to write a Java program which can generate a binary tree from a given formula like:

3 - 7 * 5 or a -> (b v b) <-> g

I already tried the Shunting-yard-Algorithmus algorithm, which is mentioned here:

Algorithm for parsing first order logic formulas

and I already understand it. therefore I have no problems to writing the Reverse Polish notation from the given formula. I still don't know how this should help me to generate a tree from that.

Community
  • 1
  • 1
noctua
  • 115
  • 10
  • I don't see a question. – user4235730 Dec 07 '14 at 01:48
  • A quick Google search on "shunting yard tree java" reveals http://stackoverflow.com/questions/21356772/abstract-syntax-tree-using-the-shunting-yard-algorithm, which links to a blog post that does exactly what you're asking. Next time, do your own research. – Jim Mischel Dec 07 '14 at 04:31
  • @user4235730 the Question is: How can i generate a tree from revese polish notation and why is it easyer in reverse polish – noctua Dec 07 '14 at 14:05
  • @Jim Mischel Oh my god, how I hate such postings like yours. If I had found that link (rather than the link i wrote) i wouldn't post here! – noctua Dec 07 '14 at 14:08

1 Answers1

0

How do you generate a tree from RPN? It's not much different from evaluating the RPN: you have a stack of values, initially empty, and you read the RPN linearly left-to-right. When you read a value, you push it omto the stack. When you read an operator, you pop the appropriate number of values, make a node with the operator, and push the nide onto the stack. If all goes well, when you have read the entire RPN expression, you have a single node on the stack which is the root of the AST.

Now, the shunting-yard algorithm produces the RPN expression linearly, left-to-right. How can you glue these two algorithms together in a way which avoids creating a temporary vector to hold the RPN? Hopefully, the answer is reaonably obvious.

rici
  • 234,347
  • 28
  • 237
  • 341