從算術表達式構造一棵樹

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實例準備成爲操作數。我可以給你更多關於如何分流操作員的詳細信息，但可能值得你首先嚐試一下。