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. — , Mar 30 '20 at 05:19
Yeah, like @PrernaGupta said it works fine either you aren't printing the return value or your tree structure is incorrect. — Dr. Confused, Mar 30 '20 at 05:23
Yea honestly i forgot to print the return value. But I did change the question somewhat after realizing that mistake. — RegeleViteaz, Mar 30 '20 at 05: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. — , Mar 30 '20 at 05:36
Can I know how you are evaluating this (2+5)/7-(21+3) to -22.6 because as per inorder traversal of the same it doers not evaluate to this. — , Mar 30 '20 at 05:51
You are going to have to create a round function for it (if I am not mistaken) will always round up. For the switch returns. — Dr. Confused, Mar 30 '20 at 05:52
Char takes exactly one byte . If there is more than 1 byte you need to store the same in char array . For reference: https://stackoverflow.com/questions/7853502/how-to-convert-parse-from-string-to-char-in-java — , Mar 30 '20 at 06:12

score 1 · Answer 1 · answered Mar 30 '20 at 06:03

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 '20 at 06:03

Thank you. However, unrelated to rounding, when I try to calculate 21+3, i get a result of 5. – RegeleViteaz Mar 30 '20 at 06:20
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. – Mar 30 '20 at 06:24
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 – Mar 30 '20 at 06:31
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.. – Mar 30 '20 at 07:04

Dr. Confused · Accepted Answer · 2020-03-30T06:56:16.833

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);

Evaluating binary tree with recursion

2 Answers2