jakeinmn - 1 year ago 235

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

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

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.