CODEWITHSUNDEEP
javarecursiontree
FatimahFatCakes
FatimahFatCakes

Reputation: 331

How to simplify an arithmetic expression tree with recursion?

How would i use recursion to simplify an expression tree? For example:

enter image description here

I've tried a few different things but I cannot figure out how to recurse through the tree in a way that i am able to simplify it. Thanks.

public static LinkedBinaryTree<String> simplify(LinkedBinaryTree<String> tree) throws IllegalArgumentException {
    // TODO: Implement this method
    if (!isArithmeticExpression(tree) || tree == null) {
        throw new IllegalArgumentException("Invalid arithmetic expression or Tree is null");
    }

    return simplify(tree.root(), tree);
}

public static LinkedBinaryTree<String> simplify(Position<String> p, LinkedBinaryTree<String> tree) {
    //      if (tree.isExternal(p)) {
    //          return tree;
    //      }
    if (isAlphaNumeric(p.getElement())) {

    }

    if (p.getElement().equals("+") || p.getElement().equals("+") || p.getElement().equals("+")) {

    }

    String element = p.getElement();
    char charLeft = tree.left(p).getElement().charAt(0);
    char charRight = tree.right(p).getElement().charAt(0);
    String stringLeft = tree.left(p).getElement();
    String stringRight = tree.right(p).getElement();

    //      if (stringLeft.equals("+") || stringLeft.equals("-") || stringLeft.equals("*")) {
    //          simplify(tree.left(p), tree);
    //      }

    //      if (!(Character.isLetter(charLeft) || Character.isDigit(charLeft))) {
    //          
    //      }

    return null;

}

Upvotes: 1

Views: 1879

Answers (2)

Schidu Luca
Schidu Luca

Reputation: 3947

This is just an example, but you can adapt it further to your needs:

int simplify(Node root) {

    if(root == null) {
        return 0;
    }
    int result;

    switch (root.value) {
        case "-":
            result = simplify(root.left) - simplify(root.right);
            break;
        case "+":
            result = simplify(root.left) + simplify(root.right);
            break;
        default:
            return Integer.parseInt(root.value);

    }
    return result;
}

So the idea is to go through your tree, you can have two case here:

  • node's value is an operand, in that case you recursively go to the right and left node while applying the given operand.

  • node's value is number, then you just return it's value.

Upvotes: 1

Adam
Adam

Reputation: 3003

Here is some pseudo code which will put you in the right direction!

public int calculate() {
    return calculateNode(rootNode)
}

private int calculateNode(Node node) {
    if (node.isOperator()){
        int operandLeft = calculateNode(node.leftChild();
        int operandRight = calculateNode(node.leftChild();
        return node.getOperator().operateOn(operandLeft, operandRight);
    } else {
        return node.getValue()      
    }
}

The function calculate() is meant to be a function on the entire tree which sets of the recursion.

And the important thing with the recursive function calculateNode(Node node) is to see the end condition of when-a-node-is-a-number but it can also be tricky sometimes to realise that the recursive function should call itself twice in a single call so to speak.

Upvotes: 1

Related Questions