jakeinmn jakeinmn - 1 year ago 266
Java Question

Creating a Binary Expression Tree given prefix notation in java

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

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

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.

Answer Source

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


* + 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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download