function - 使用二叉树对整数上的中缀算术表达式进行编码

Question

这是 aws education 提出的问题。我已经思考这个问题很长时间了，但没有真正取得任何进展。

You want to use a binary tree to encode infix arithmetic expressions on integers. Operations are addition and multiplication Draw a picture of what the tree looks like. Write a class definition. Write an evaluate() member function. How would you make your evaluate() iterative instead of recursive

如果我能得到一个解释或者一些例子就好了

Answer 1

插图 - 对整数上的中缀算术表达式进行编码的二叉树

如您所见，叶子是值(或文字)，其他节点包含算术运算符(+、-、/、*)

一些代码 - 回避

在Java中，可以使用递归来解决这个问题(前提是树的高度不太大)

public class Main {

    public static void main(String[] args) {
        // op1=(1 + 2)
        Node op1 = new Node(1, "+", 2);
        System.out.println("op1="+op1.evaluate()); // op1=3

        // op2=(1 + 2) + 3
        Node op2 = new Node(op1, "+", 3);
        System.out.println("op2="+op2.evaluate()); // op2=6

        // op3=(4 * 5)
        Node op3 = new Node(4, "*", 5);
        System.out.println("op3="+op3.evaluate()); // op3=20

        // op4=((1+2)+3)*(4*5)
        Node op4 = new Node(op2, "*", op3);
        System.out.println("op4="+op4.evaluate()); // op4=120
    }
}

class Node {

    private Node left;
    private Node right;
    private String operatorOrLiteral;

    public Node(String value){
        this.operatorOrLiteral = value;
    }

    public Node(Node left, String operation, Node right){
        this.operatorOrLiteral = operation;
        this.left = left;
        this.right = right;
    }

    public Node(int literal1, String operation, int literal2){
        this(new Node(Integer.toString(literal1)), operation, new Node(Integer.toString(literal2)));
    }

    public Node(Node left, String operation, int literal2) {
        this(left, operation, new Node(Integer.toString(literal2)));
    }

    public Node(int literal1, String operation, Node right) {
        this(new Node(Integer.toString(literal1)), operation, right);
    }

    public int evaluate(){
        if(isLiteral()) {
            return Integer.parseInt(operatorOrLiteral);
        }

        switch (operatorOrLiteral) {
            case "*": return left.evaluate() * right.evaluate();
            case "/": return left.evaluate() / right.evaluate();
            case "-": return left.evaluate() - right.evaluate();
            case "+": return left.evaluate() + right.evaluate();
            default: throw new IllegalArgumentException(operatorOrLiteral + " is not recognised");
        }
    }

    private boolean isLiteral() {
        return left == null && right == null;
    }

    public String toString() {
        if(isLiteral()) {
            return operatorOrLiteral;
        }

        return "(" + left.toString() + operatorOrLiteral + right.toString() + ")";
    }
}

一些代码 - 迭代

或者正如 @David Sanders 所提到的，您可以使用树遍历。