求解给定变量的二叉表达式树

Question

对于表达式：

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

我的程序构建了以下二叉树：

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

为了得到变量v的解，我手动这样解：

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

如何以编程方式执行相同的操作？

例如，给定二叉树及其特定节点（在本例中为 v），重建这棵树，使其计算为该节点：

(=)
 ├─ (v) <-- my node
 └─ (-)
     ├─ (10)
     └─ (/)
         ├─ ...
         └─ ...

Answer 1

首先对 input/output 发表一些评论：

运算符的第一个操作数在树表示中应该始终是 left child，而第二个操作数应该是 right child.

因此，由于 3 是除数（因此是除法的第二个操作数），它应该作为 second [=62] 在输入树中出现=].所以 res = ((v + 10) * (i - 2)) / 3 的输入树应该是：

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

同样，输出应该有 10 作为 - 节点的第二个 child：

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

一些（其他）假设：

根应该有=作为符号，并且有两个children.
目标符号（此处为“v”）应该只出现一次。
non-root运算符应该是+、-、*或/，并且应该是有两个children的节点（二进制）。
Non-operator 节点应该是叶子。

这是 JavaScript 中的一个实现，它定义了一个 Node class，包括将改变其子树以便将目标节点置于等式左侧的方法以及右侧的所有其余部分：

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

当然，这可以扩展以处理更多场景，例如求幂、目标符号多次出现、求解多项式等。然而，这超出了问题的范围。

求解给定变量的二叉表达式树

Solve binary expression tree for given variable

algorithm

tree

binary-tree

tree-traversal