java - 递归下降解析器 - 添加统一变量

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 ，因此每个分支都会自下而上求值，直到最终得到 1 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”。

如果您想变得更加复杂，您可以在运算符(operator)中建立关联和分发意识并更改 simplify以便它重新组织树以对变量进行分组。但我相信这有点超出了这个问题的范围!