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

Question

这是来自 aws educate 的问题。这个问题我想了好久了，一直想不通。

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

题目要求你写一棵树class，它可以表示像“2 + 2”或“3 * 1 + 5”这样的表达式。所以 class 代表一棵树，它有根和内部节点，对应于“*”或“+”运算符的应用。叶节点将对应于正在操作的整数值，如“5”或“2”。从这种树中产生结果的典型评估函数可能是递归的。他们还要求您考虑如何迭代地得出结果。这种迭代方法可能涉及将节点连续添加到队列或堆栈数据结构中，然后将它们一个接一个地弹出以进行某种处理。

看这里：https://en.wikipedia.org/wiki/Tree_traversal

Answer 2

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

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

一些代码 - 回避

在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 所述，您可以使用树遍历。

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

use a binary tree to encode infix arithmetic expressions on integers

binary-tree

class

function

infix-notation