java - 从算术表达式构造树

Question

目前我对如何实现这棵树感到非常困惑，我正在尝试从输入“(4 + 6) + (2 + 3)”的字符串表示形式构造一棵树。我将如何用两个堆栈制作一棵树？

  public class Tree {

        private Stack opStk = new Stack();
        private Stack valStk = new Stack();
        private Tree parent = null;


        public Tree(String str){

            System.out.println((EvaluateExpression(str)));

        }   

        public void doOperation() { 

        Object x = valStk.pop();
        Object y = valStk.pop();
        Object op = opStk.pop();

        if ((Integer) x <= 0 || (Integer) y <= 0){ 
            throw new NumberFormatException();
        }
        if (op.equals("+")) {
            int sum = (Integer) x + (Integer) y;
            valStk.push(sum);
        }

        }

        public void repeatOps(char refOp) { 

            while (valStk.count() > 1 && 
                prec(refOp) <= prec((char)opStk.pop())) { 
                doOperation();  
            }   

        }

        int prec(char op) {
            switch (op) {

                case '+':
                case '-':
                    return 0;
                case '*':
                case '/':
                    return 1;
                case '^':
                    return 2;

                default:
                    throw new IllegalArgumentException("Operator unknown: " + op);
            }
        }

        public Object EvaluateExpression(String str) { 

            System.out.println("Evaluating " + str);
            Scanner s = null;

            try {
                s = new Scanner(str);

                //while there is tokens to be read
               while (s.hasNext()) {

                   //if token is an int
                  if (s.hasNextInt()) {
                      //read it 
                    int val = s.nextInt();
                    if(val <= 0) { 
                        throw new NumberFormatException("Non-positive");
                    }
                    System.out.println("Val " + val);
                    //push it to the stack
                    valStk.push(val);
                  } else { 
                      //push operator
                      String next = s.next();
                      char chr = next.charAt(0);
                      System.out.println("Repeat Ops " + chr);
                      repeatOps(chr);
                      System.out.println("Op " + next);
                      opStk.push(chr);
                  }
                  repeatOps('+');
                }  

            } finally {
                if (s != null) {
                    s.close();
                }
            }

            System.out.println("Should be the result: " + valStk.pop());
           return valStk.pop();

        }

Answer 1

我有一些建议可以让您走上正确的道路(希望如此)。

首先我建议你的表达式树遵循 Composite Design Pattern 。它非常适合这些类型的层次结构。出于您的目的，它看起来像:

interface Expression {
    int getValue();
}

class Constant implements Expression {
    private int value;
    public int getValue() {
        return value;
    }
}

class Operation implements Expression {
    private Expression operand1;
    private Operator operator;
    private Expression operand2;
    public int getValue() {
        return operator.apply(operand1, operand2);
    }
}

请注意，您不需要任何运算符优先级或括号的概念:它完全隐含在树的构造方式中。例如，“3 + 4 * 2”应生成树“(+ 3 (* 4 2))”，而“(3 + 4) * 2”应生成树“(* (+ 3 4) 2) ”。

其次，我建议您将运算符放入枚举中，而不是依赖于字符串值:

enum Operator {
    TIMES((n1, n2) -> n1 * n2),
    DIVIDE((n1, n2) -> n1 / n2),
    PLUS((n1, n2) -> n1 + n2),
    MINUS((n1, n2) -> n1 - n2);

    private final BinaryOperator<Integer> operation;
    Operator(BinaryOperator<Integer> operation) {
        this.operation = operation;
    }
    public int apply(int operand1, int operand2) {
        return operation.apply(operand1, operand2);
    }
}

这种方法的优点是添加新运算符很简单，而无需更改树的结构。

第三，我建议您将从字符串到表达式树的转换分为两个步骤。第一个是将字符串转换为标记，第二个是将标记转换为树。这些在行话中称为词汇和语义分析。

如果您使用调车场算法进行语义分析，请记住输出堆栈将保存准备成为操作数的 Expression 实例。我可以为您提供有关如何分流运算符(operator)的更多详细信息，但您可能值得先尝试一下上述建议。