Creating a Binary Expression Tree given prefix notation in java

Question

How should we construct the binary tree of the following "prefix" order expression?

( - * / 8 + 5 1 4 + 3 - 5 / 18 6 ) 4

Pseudocode is like this:

public ExpressionRootNode MakeBinaryTree(expr):
    element = next element in expr
    if element is a number:
        return a leaf node of that number
    else: // element is an operator
        left = MakeBinaryTree(expr)
        right = MakeBinaryTree(expr)
        return a binary tree with subtrees left and right and with operator element
        //^aka return root

However, I dont quite understand how to recursively call the function to create said tree. I have tried looking at how to Create a binary tree from an algebraic expression, but can't figure out how to backtrack up to the other node.

Project files : http://pastebin.com/BJiPtDM5, its a mess.

How about **returning** it? Not all methods must be `void` you know. — Ingo, Nov 23 '13 at 23:31
Edited the pseudocode to change from void -> ExpressionRootNode — jakeinmn, Nov 23 '13 at 23:33
Good! You have the operation, the left subtree and the right subtree. What exactly is your problem to create the corresponding Tree instance? — Ingo, Nov 23 '13 at 23:35
Doesn't the function need to call itself WITH its parent root? How will it know who's left and whose right to be called? Would this.left and this.right work? — jakeinmn, Nov 23 '13 at 23:39

Ingo · Accepted Answer · 2013-11-23T23:59:16.763

1

More pseudocode:

abstract class Tree { .... }
class Leave extends Tree { int number; ... }
class Expr  extends Tree { Tree left, right; String operation;  .... }

public Tree makeBinaryTree(expr):
   element = next element in expr
   if element is a number:
      return new Leave(element)
   else: // element is an operator
      left = makeBinaryTree(expr)
      right = makeBinaryTree(expr)
   return new Expr(left, right, element)

The constructors of Leave/Expr are expected to just set the fields from their arguments.

What is left to be done is some error handling, though. Ohh, and make sure that "next element in expr" also removes the part already dealt with.

Given a correct input, it will work like this:

if the input is just a number, it will return a Leave with that number
if the input is of the form OP L R, it will remember OP, make the left subtree from L and the right subtree from R and return that as expression.
no other inputs are possible/valid

Example:

* + 5 1 7

will result in:

Expr(Expr(Leave(5), Leave(1), "+"), Leave(7), "*")

Note that those prefix expressions cannot see if "-" is supposed to be unary negation or binary subtraction. Hence you can't use the same operator character for that.

edited Nov 23 '13 at 23:59

answered Nov 23 '13 at 23:44

Ingo

36,037
5
53
100

This doesnt account for setting the root node. It will create a null root with left and right childs. Root will be blank. – jakeinmn Nov 24 '13 at 02:20
http://pastebin.com/izcuMTuZ this is what I got with your code. I'm trying to create a ExpressionTree. Do I just call makeBinaryTree in ExpressionTree's constructor, and then just cast (ExpressionTree) to the result of makeBinaryTree? – jakeinmn Nov 24 '13 at 03:02
I managed to get it I think. All I need to do is figure out how to turn this tree of Expr's into one whole ExpressionTree. – jakeinmn Nov 24 '13 at 03:48
http://pastebin.com/s1RxYN7x ... Also weird that I cant call root.data http://i.imgur.com/g62a064.png – jakeinmn Nov 24 '13 at 03:54
@jakeinmn Yes, it creates a tree, and that's it. If you need to set some variable (root node?), you can do that in a method that calls this. I am not sure what you mean with ExpressionTree? Please show your definition of it. The code is thought to get adapted to your data structure. – Ingo Nov 24 '13 at 10:30

score -2 · Answer 2 · edited May 23 '17 at 12:08

-2

See the last two answers here.

parsing math expression in c/c++

I think they are quite useful.

You need a formal grammar and then a recursive descent parser. Not sure if you're fully familiar with these two concepts. If not, you should read some more about them.

edited May 23 '17 at 12:08

Community

1
1

answered Nov 23 '13 at 23:36

peter.petrov

38,363
16
94
159

Sorry, he doesn't need a recursive descent parser for this. – Ingo Nov 23 '13 at 23:37
OK... Could be. Just a stack maybe? :) – peter.petrov Nov 23 '13 at 23:41
His pseudo code is already good. He's just a bit confused about parameter passing. – Ingo Nov 23 '13 at 23:45

Creating a Binary Expression Tree given prefix notation in java

2 Answers2