递归下降解析器 - 添加初始化变量

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() return 行是 double，我的解析器的工作方式是每个表达式节点 return 是 double，所以每个分支都是自下而上求值的，直到它最终以一个 double 答案结束。

问题是，我想在我的表达式中处理单元化变量，就像这样如果我想解析 5 + x（其中 x 没有事先初始化）表达式的值将 return 5 + x。

我是否必须将表达式节点的 getValue() return 类型更改为 String？我觉得这会使程序复杂化和膨胀，必须有更好的方法来实现这一点。有没有人有过这类事情的经验？

我知道我的解析器的描述可能有点模糊，所以 this 是我学习如何实现它的大部分内容的地方。

Answer 1

我假设在你的表达式树中你已经为运算符和常量定义了 classes。您需要为变量定义一个新的 class。

然后您将需要添加一个类似 getAllVariables 的方法，它可以 return 树中任何点下方的所有变量。

我建议您更改 getValue 以接受 Map<String, Double> 以在评估时为任何变量提供值。这将需要被除变量以外的所有节点忽略，这些变量将从地图中 return 它们自己的值。如果他们没有为自己找到一个映射作为键，他们应该抛出一个 EvaluationException.

最后，如果您希望能够将表达式打印为字符串，那么这确实是您 getValue 的一个单独方法。也许getExpressionText。然后每个 class 都可以将其覆盖为 return 一个表示从该点开始的表达式的字符串，变量只是 return 变量名。

所以现在一旦你解析了你的表达式你就可以得到所有的变量，提示用户输入它们的值，计算给定值的表达式（如果有任何未定义则捕获异常）并再次打印出来。

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 class 最终看起来像这样：

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);
    }
}

您可能希望对表达式树执行的另一个常见操作是简化它。这本质上意味着将任何可以评估的东西评估为常数。在我看来，最好的方法是 return 一个新的简化树而不是改变当前的树。所以我建议添加一个新方法到 ExpressionNode:

public ExpressionNode simplify();

对于变量和常量，这只是 return 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());

这将 return "14 + x * 3".

如果您随后想要变得更加复杂，您可以在运算符中建立关联和分布的意识并更改 simplify 以便它重新组织树以对变量进行分组。但我认为这有点超出了这个问题的范围！

递归下降解析器 - 添加初始化变量

Recursive Descent Parser - Adding Unitialized Variables

java

parsing