Evaluating binary tree with recursion

Question

I have a binary tree containing integers in the external nodes and operators in the internal nodes.
I send the root node of the tree to my evaluateTree method.
I want to traverse the tree and to calculate the final result.
The node class's fields are

private Node left;
private Node right;
char value;

For example, I want to evaluate (2+5)/8-(21+3) should equal, with rounding, to -23.
When I try to do so, I get a result of -5. Unrelated to rounding, when I try to calculate 21+3, i get a result of 5. Any guidance would be appreciated.

int evaluateTree(Node node)
{
   System.out.println("Inside evaluateTree");
   if (Character.isDigit(node.value))
   {
      return Character.getNumericValue(node.value);
   }
   else
   {
      int operand1 = evaluateTree(node.left);
      int operand2 = evaluateTree(node.right);
      switch (node.value)
      {
         case '+':
            return (int) Math.round(operand1 + operand2);
         case '-':
            return (int) Math.round(operand1 - operand2);
         case '*':
            return (int) Math.round(operand1 * operand2);
         case '/':
            return (int) Math.round(operand1 / operand2);
         default:
            throw new IllegalStateException("Unexpected value: " + node.value);
       }
   }
}

This is how i create my tree

public void createTree()
{
   Scanner keyboardInput = new Scanner(System.in);
   ArrayList<String> postFixArray = new ArrayList<>();
   postFixArray = getPostFixString("(21+3)");
   System.out.println("\nCREATE TREE PRINTING\n");
   System.out.println(postFixArray);
   Stack<Node> nodeStack = new Stack<>();
   while (!postFixArray.isEmpty())
   {
      String temp = postFixArray.get(0);
      char charTemp = temp.charAt(0);
      if (!isOperator(charTemp))
      {
         if (!Character.isDigit(charTemp))
         {
            System.out.println("Enter the integer value for your variable " + charTemp + ": ");
            int setVarValue = keyboardInput.nextInt();
            for (int i = 0; i < postFixArray.size(); i++)
            {
                if (charTemp == postFixArray.get(i).charAt(0))
                {
                     postFixArray.set(i, String.valueOf(setVarValue));
                }
            }
         }
         String tempLink = postFixArray.remove(0);
         char nodeData = tempLink.charAt(0);
         Node leaf = new Node(nodeData);
         nodeStack.push(leaf);
      }
      else
      {
         if (nodeStack.size() >= 1)
         {
            String tempLink = postFixArray.remove(0);
            char nodeData = tempLink.charAt(0);
            Node leaf = new Node(nodeData);
            leaf.right = nodeStack.pop();
            leaf.left = nodeStack.pop();
            nodeStack.push(leaf);
         }
      }
   }
   Node root = nodeStack.pop();
   System.out.println(root);
   System.out.println(evaluateTree(root));
}

For which example it is not working . I have tried with 2+5 and it works fine. — user11935734
– user11935734, Commented Mar 30, 2020 at 5:19
Yeah, like @PrernaGupta said it works fine either you aren't printing the return value or your tree structure is incorrect. — Dr. Confused
– Dr. Confused, Commented Mar 30, 2020 at 5:23
Yea honestly i forgot to print the return value. But I did change the question somewhat after realizing that mistake. — RegeleViteaz
– RegeleViteaz, Commented Mar 30, 2020 at 5:25
Example that you have mentioned above, ((2+5)/7-(21+3)) is it working in above code. Since in your Node you are taking value as char , but 21 is not a char value and it will give error. — user11935734
– user11935734, Commented Mar 30, 2020 at 5:36

Dr. Confused · Accepted Answer · 2020-03-30 06:56:16Z

Rounding

To round the values just add a round function to the returns of the switch statements. The division you should cast it to a double or a float since it will be rounded up if you don't.

switch (node.value)
{
    case '+':
        return round(operand1 + operand2);
    case '-':
        return round(operand1 - operand2);
    case '*':
        return round(operand1 * operand2);
    case '/':
        return round((float) operand1 / operand2);
    default:
        throw new IllegalStateException("Unexpected value: " + node.value);
}

-

public static int round(double x) {
    return (int) Math.round(x);
}

For the validating if there is an integer with more than one digit you should probably use Regex, but this problem should have its own dedicated question.

EDIT: I created some test cases without a tree creation method to test out if this chuck of code was working correctly. It passed the following tests:

    // 21/3 = 7
public static void testCaseOne() {
    Node three = new Node(null, null, '3');
    Node nine = new Node(null, null, '9');
    Node nine2 = new Node(null, null, '9');
    Node three2 = new Node(null, null, '3');
    Node plus3 = new Node(nine, three, '+');
    Node plus2 = new Node(nine2, plus3, '+');
    Node plus = new Node(plus2, three2, '/');
    System.out.println("PASSED: " + (evaluateTree(plus) == 7) + " " + evaluateTree(plus));
}

// 21+3 = 24
public static void testCaseTwo() {
    Node three = new Node(null, null, '3');
    Node nine = new Node(null, null, '9');
    Node nine2 = new Node(null, null, '9');
    Node three2 = new Node(null, null, '3');
    Node plus3 = new Node(nine, three, '+');
    Node plus2 = new Node(nine2, plus3, '+');
    Node plus = new Node(plus2, three2, '+');
    System.out.println("PASSED: " + (evaluateTree(plus) == 24) + " " + evaluateTree(plus));
}

// 9/9/3/3 = 1
public static void testCaseThree() {
    Node three = new Node(null, null, '3');
    Node nine = new Node(null, null, '9');
    Node nine2 = new Node(null, null, '9');
    Node three2 = new Node(null, null, '3');
    Node plus3 = new Node(nine, three, '/');
    Node plus2 = new Node(nine2, plus3, '/');
    Node plus = new Node(plus2, three2, '/');
    System.out.println("PASSED: " + (evaluateTree(plus) == 1) + " " + evaluateTree(plus));
}

// 21/2 = 10.5 = 11
public static void testCaseFour() {
    Node three = new Node(null, null, '3');
    Node nine = new Node(null, null, '9');
    Node nine2 = new Node(null, null, '9');
    Node two = new Node(null, null, '2');
    Node plus3 = new Node(nine, three, '+');
    Node plus2 = new Node(nine2, plus3, '+');
    Node plus = new Node(plus2, two, '/');
    System.out.println("PASSED: " + (evaluateTree(plus) == 11) + " " + evaluateTree(plus));
}

// 22/3 = 7.33 = 7
public static void testCaseFive() {
    Node four = new Node(null, null, '4');
    Node nine = new Node(null, null, '9');
    Node nine2 = new Node(null, null, '9');
    Node three2 = new Node(null, null, '3');
    Node plus3 = new Node(nine, four, '+');
    Node plus2 = new Node(nine2, plus3, '+');
    Node plus = new Node(plus2, three2, '/');
    System.out.println("PASSED: " + (evaluateTree(plus) == 7) + " " + evaluateTree(plus));
}

Validating

To further add on the validating input you could do something like:

String regexExpression = "([()\\-+/0-9]+)?\\d{2}([()\\-+/0-9]+)?";
String str = "(2+5)/8-(21+3)";
boolean containsLongInts = str.matches(regexExpression);
System.out.println(str + " contains long ints: " + containsLongInts);

String str2 = "(2+5)/8-(2+3)";
boolean containsLongInts2 = str2.matches(regexExpression);
System.out.println(str2 + " contains long ints: " + containsLongInts2);

user11935734 · Accepted Answer · 2020-03-30 06:03:51Z

1

For rounding the value returned, you can change return type of evaluateTree to Doubleand then use Math.round to round of the value, which will return an int value.

Here is the update code of function evaluateTree :

public static Double   evaluateTree(Node node)
{
   System.out.println("Inside evaluateTree");
   if (Character.isDigit(node.value))
   {
      return (double)Character.getNumericValue(node.value);
   }
   else
   {
      double operand1 = evaluateTree(node.left);
      double operand2 = evaluateTree(node.right);
      switch (node.value)
      {
         case '+':
            return operand1 + operand2;
         case '-':
            return operand1 - operand2;
         case '*':
            return operand1 * operand2;
         case '/':
            return operand1 / operand2;
         default:
            throw new IllegalStateException("Unexpected value: " + node.value);
       }
   }
}

At the end wherever you are calling this method you can return its value as

Math.round(evaluateTree(root))

answered Mar 30, 2020 at 6:03

user11935734

4 Comments

RegeleViteaz Over a year ago

Thank you. However, unrelated to rounding, when I try to calculate 21+3, i get a result of 5.

user11935734 Over a year ago

Can you share the code of how you are creating nodes for the above expression because I am not sure how you are adding 21 to your Node value field as it is char.

user11935734 Over a year ago

I am assuming in whatever way you are adding value to your value field in Node , it is taking just first char. Exampe result of this (2+5)/8-(21+3) as mentioned by you is -5, since from 21 it is taking just 2 . So, it transfers to (2+5)/8-(2+3) => 7/8 - 5 =>0 -5 =-5 . Same is happening with 21+3 => 2+3 =5 . This is just my assumption . We can verify the same once you paste code to show how you are creating nodes of such expression

user11935734 Over a year ago

Just saw you code . For creating leaf node you are calcualating value of leaf node by doing String tempLink = postFixArray.remove(0); char nodeData = tempLink.charAt(0);. Now suppose postFixArray.charAt(0) value is 24 and then you are doing "24".charAt(0) which gives result as 2 and your leaf node gets created with value as 2 not 24. So, same thing that I have mentioned in my above comment is happening you are creating nodes of digit by extracting first char value of string , and not using whole string because of which it works fine for 0-9 , but after that only first character is used..

Collectives™ on Stack Overflow

Evaluating binary tree with recursion

2 Answers 2

Comments

4 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Linked

Related