遞歸下降解析器 - 添加單元化變量

Question

所以，我有一個遞歸下降解析器，用於分析中綴數學表達式。該表達式被標記化，用前面提到的解析器進行解析，解析器可以即時生成AST（每種表達式都有節點）並計算最終值。我正在處理所有這些值爲doubles;所以，我用這個解析器像這樣：

Parser parser = new Parser(); 

try { 
    ExpressionNode expression = parser.parse("5 + 4*cos(pi)"); 
    System.out.println("The value of the expression is " 
      + expression.getValue()); 
} catch (ParserException | EvaluationException e) { 
    System.out.println(e.getMessage()); 
} 

}

隨着Exceptions我定義自己。 行expression.getValue()返回一個double，我的解析器工作的方式是每個表達式節點返回一個double，因此每個分支都是自下而上評估的，直到它最終以一個double答案結束。

的事情是，我想處理未初始化變量在我的表情，像這樣如果我想解析5 + x（其中x是不是之前初始化）表達式的值將返回5 + x。

我將不得不將我的表達式節點的getValue()返回類型更改爲String？我覺得這會讓這個計劃變得複雜和膨脹，並且必須有更好的方法來實現這一目標。有沒有人有這種類型的事情的經驗？

我知道我的解析器的描述可能有點模糊，所以this是我學習如何實現它的大部分內容。

Answer 1

我在你的表達式樹中假設你有爲操作符和常量定義的類。您將需要爲變量定義一個新類。

然後，您需要添加一個方法，如getAllVariables，它可以返回樹下任意點以下的所有變量。

我建議你將getValue更改爲接受Map<String, Double>以在評估時間爲任何變量提供值。除了會從地圖返回它們自己的值的變量之外，這將需要被所有節點忽略。如果他們沒有找到自己的映射作爲關鍵，他們應該拋出一個EvaluationException。

最後，如果您希望能夠將表達式打印爲字符串，那麼這對您的getValue來說實在是一種單獨的方法。也許getExpressionText。然後每個類都可以覆蓋它，以返回一個代表該表達式的字符串，該變量只是返回變量名稱。

所以，現在一旦你解析了你的表達式，你就可以得到所有的變量，提示用戶輸入它們的值，評估給定值的表達式（如果有未定義的話捕獲異常）並再次打印出來。

ExpressionNode expression = Parser.parse("x + 5 * y"); 
System.out.println(expression.getExpressionText()); 
System.out.println(expression.getAllVariables()); 
Map<String, Double> variableValues = new TreeMap<>(); 
variableValues.put("x", 4); 
variableValues.put("y", -2); 
System.out.println("Evaluates to " + expression.getValue(variableValues)); 

我希望你Variable類最後看起來是這樣的：

public class Variable implements ExpressionNode { 
    private final String name; 

    public double getValue(Map<String, Double> variableValues) { 
     if (variableValues.containsKey(name)) { 
      return variableValues.get(name); 
     } else { 
      throw new EvaluationException(name + " is undefined"); 
     } 
    } 

    public String getExpressionText() { 
     return name; 
    } 

    public List<String> getAllVariables() { 
     return Arrays.asList(name); 
    } 
} 

你可能想在一個表達式樹進行另一種常見的操作是簡化它。這基本上意味着評估一個可以評估的東西。在我看來，最好的辦法是返回一個新的簡化樹，而不是改變當前樹。所以我建議增加一個新的方法來ExpressionNode：

public ExpressionNode simplify(); 

對於變量和常量，這將只返回this。對於運營商來說，它需要做更復雜的事情。像這樣：

class Operator implements ExpressionNode { 
    public ExpressionNode simplify() { 
    if (getAllVariables().isEmpty()) { 
     return new Constant(getValue()); 
    } else { 
     Operator simplified = new Operator(operation); 
     for (ExpressionNode operand: operands) { 
      simplified.addOperand(operand.simplify()); 
     } 
     return simplified; 
    } 
} 

希望你看看有什麼。如果操作可以完全評估，那麼它將轉換爲常量。否則，它仍然是一個操作，但它的每個操作數依次被簡化。

所以，現在如果你想簡化你可以做一個表情：

System.out.println(Parser.parse("7 * 2 + x * 3").simplify().getExpressionText()); 

將返回 「14 + X * 3」。

如果您希望變得更加複雜，您可以建立關聯和分配意識到您的操作員，並更改simplify，以便將樹重新組織到組變量。但我相信這超出了這個問題的範圍！