How do i now "build" the tree using a scanner? (explanation after code)

Question

The assignment is meant to help understand and practice tree concepts and traversal. I am supposed to use the tree to evaluate the expression in prefix (polish) notation as well as printing the expression in postfix(reverse polish) notation and infix notation.

Here is the Evaluation class that was given.

 import java.util.*;
 public class Evaluation
 {
public static void main(String[] args)
{
    System.out.print("Enter a prefix expression:  ");
    Scanner scanner = new Scanner(System.in);

    // build an expression tree
    Node root = buildTree(scanner);

    // print prefix expression
    System.out.println("prefix expression:");
    preorder(root);
    System.out.println();

    // print postfix expression
    System.out.println("postfix expression:");
    postorder(root);
    System.out.println();

    // print infix expression
    System.out.println("infix expression:");
    inorder(root);
    System.out.println();

    // evaluate the expression using postfix
    System.out.println("Result = " + evaluate(root));
}

// build an expression tree and return the root node of the tree
public static Node buildTree(Scanner sc)
{
    // your code here

}

// Postfix expression is the result of a post-order traversal
public static void postorder(Node node)
{
    // your code here

}

// Prefix expression is the result of a pre-order traversal
public static void preorder(Node node)
{
    // your code here

}

// Infix expression is the result of a in-order traversal
public static void inorder(Node node)
{
    // your code here

}

// Evaluate the expression tree using postorder traversal
public static int evaluate(Node node)
{
    // your code here

}
 }

EDIT: Here is the Node class, that I had to write.

 public class Node {
String value;
Node left, right;

Node(String value){
    this.value = value;
}

Node(String value, Node left, Node right){
    this.left = left;
    this.right = right;

}

public boolean isLeaf(){
    if()

    return true;
}

 }

The instructions on the assignment were to use the given method buildTree to construct a tree and evaluate 4 given expressions in prefix notation:

1.- + 10 * 2 8 3

2./ * + 3 14 2 7

3.+ + 4 2 * 3 - 15 1

4./ - % + 1 2 3 6 + 2 3

EDIT: In a previous assignment I had to evaluate Postfix expressions using a stack, but how would I build and traverse using this tree to evaluate prefix expressions? (I assume that operands and operators would be the value of the nodes and then the nodes would link in some way.)

Answer 1

Well, let's think about it. What makes a node to be a leaf?

I'd say that a leaf is a node with no children. So, what about using the following boolean expression for your if check: if(left == null && right == null)?

LATER EDIT: in fact, you don't even need an if check. You can put it simply like

public boolean isLeaf(){
    return left == null && right == null;
}

Also, please be aware that your overloaded constructor

Node(String value, Node left, Node right){
    this.left = left;
    this.right = right;

}

is not properly assigning the value.

Answer 2

I would expect that, if it is a leaf node, it will not have any references to other nodes, hence the left node, and the right node will be null. You can use this to check if it is a leaf node, by applying a check for both, and return true, if both the nodes are referencing null.

if(left == null && right == null)
    return true;
else
    return false;