Solve binary expression tree for given variable

user_7401478 0
Viewed 206

For the expression:

res = ((v + 10) * (i - 2)) / 3

My program builds the following binary tree:

(=)
 ├─ (res)
 └─ (/) 
     ├─ (3) 
     └─ (*) 
         ├─ (+)
         │   ├─ (v)
         │   └─ (10)
         └─ (-)
             ├─ (i)
             └─ (2)

To obtain a solution for variable v, I manually solve it like this:

((v + 10) * (i - 2)) / 3 = res
(v + 10) * (i - 2) = res * 3
v + 10 = (res * 3) / (i - 2)
v = ((res * 3) / (i - 2)) - 10

How can I programmatically do the same operation?

For example, given the binary tree and its specific node (in this case v), rebuild this tree so that it evaluates to that node:

(=)
 ├─ (v) <-- my node
 └─ (-)
     ├─ (10)
     └─ (/)
         ├─ ...
         └─ ...
binary-tree tree tree-traversal algorithm
1 Answers

First some comments on the input/output:

The first operand of an operator should consistently be a left child in the tree representation, while the second operand should be a right child.

So, since 3 is a divisor (and thus the second operand of a division), it should occur in the input tree as a second child. So the input tree for res = ((v + 10) * (i - 2)) / 3 should be:

(=)
 ├─ (res)
 └─ (/)
     ├─ (*)
     │   ├─ (+)
     │   │   ├─ (v)
     │   │   └─ (10)
     │   └─ (-)
     │       ├─ (i)
     │       └─ (2)
     └─ (3)

Similarly, the output should have 10 as the second child of the - node:

(=)
 ├─ (v)
 └─ (-)
     ├─ (/)
     │   ├─ (*)
     │   │   ├─ (3)
     │   │   └─ (res)
     │   └─ (-)
     │       ├─ (i)
     │       └─ (2)
     └─ (10)

Some (other) assumptions:

  • The root should have = as symbol, and have two children.
  • The target symbol (here "v") should only occur once.
  • The non-root operators should be +, -, * or /, and should be nodes with two children (binary).
  • Non-operator nodes should be leaves.

Here is an implementation in JavaScript, which defines a Node class, including the method that will mutate its subtrees so to bring the target node at left side of the equation and all the rest at the right side:

class Node {
    constructor(symbol, left=null, right=null) {
        this.symbol = symbol;
        this.left = left;
        this.right = right;
    }
    toString() {
        return !this.left && !this.right ? "(" + this.symbol + ")"
            : "(" + this.symbol + ")\n"
            + " ├─ " + this.left.toString().replace(/\n/g, "\n │  ") + "\n"
            + " └─ " + this.right.toString().replace(/\n/g, "\n    ");
    }
    markPathTo(target, found=false) {
        if (this.left) this.left.markPathTo(target, found);
        if (this.right) this.right.markPathTo(target, found);
        if (this.mark) {
            if (found) throw "symbol (" + target + ") occurs more than once";
            found = true;
        }
        this.mark = this.symbol == target || this.left && this.left.mark || this.right && this.right.mark;
    }
    resolve(target) {
        if (this.symbol != "=") throw "Can only resolve an equality, not (" + symbol  + ")";
        this.markPathTo(target);
        if (!this.mark) throw "Could not find symbol (" + target + ")";
        // Make sure the target is in the left subtree
        if (!this.left.mark) {
            // swap sides of equation
            [this.left, this.right] = [this.right, this.left];
        }
        let operators = {
            "+": "-",
            "-": "+",
            "*": "/",
            "/": "*"
        };
        let op = this.left.symbol;
        while (op !== target) {
            if (!(op in operators)) throw "Unsupported operator (" + op + ")";
            let toMove = this.left.left.mark ? this.left.right : this.left.left;
            if (op === "+" || op === "*" || this.left.right.mark) {
                this.right = new Node(operators[op], this.right, toMove);
            } else {
                this.right = new Node(op, toMove, this.right);
            }
            this.left = this.left.left.mark ? this.left.left : this.left.right;
            op = this.left.symbol;
        }
    }
}

// Demo tree from question (with corrected position of 3)
let tree = new Node("=",
    new Node("res"),
    new Node("/",
        new Node("*",
            new Node("+",
                new Node("v"),
                new Node(10)
            ),
            new Node("-",
                new Node("i"),
                new Node(2)
            )
        ),
        new Node(3)
    )
);

// Display the input tree
console.log(tree.toString());

// Apply the algorithm
tree.resolve("v");

// Display the resulting tree
console.log(tree.toString());

Of course, this could be extended to deal with more scenarios, like exponentiation, multiple occurrences of the target symbol, where polynomials are resolved, ...etc. This is however beyond the scope of the question.

user_54598390
Related