使用访问者模式的表情评估 [英] Expression evaluation using visitor pattern

问题描述

我一直在尝试使用访问者框架设计一个表达式评估器. 在进行当前设计之前，这里要解决的几个问题.

I have been trying to design an expression evaluator using visitor framework. Before going into my current design here are few problems that I am facing.

1. 当前的设计可以很好地与算术运算符配合使用，但是当涉及到逻辑运算符时，例如5 > 6将输出到false，则它不起作用.由于Visitor是通用接口，因此如果我说Visitor<Boolean>，则返回值将变为boolean，但参与的值是integer，因此我无法将整数作为参数.
2. 该设计要求每个操作员都有一个类，可以将其最小化吗?
3. 请分享您对设计的意见.它看起来不错还是需要任何修改.

1. Current design works well with arithmetic operators but when it comes to logical operators for eg 5 > 6 will output to false it doesn't work. As Visitor is a generic interface so if I say Visitor<Boolean> the return value will become boolean but participating values are integer hence I am not able to have integer as parameter.
2. The design requires a class for every operator can it be minimized?
3. Please share your inputs on design. Does it look good or any modification needed.

以下是参与课程.

这是访问者界面

public interface Visitor<T> {

    T visit(Expression expression);

    T visit(BinaryExpression binaryExpression);

    T visit(ConstantExpression expression);
}

访客实施

public class ExpressionVisitor<T> implements Visitor<T> {

    @Override
    public T visit(Expression expression) {
        return expression.accept(this);
    }

    @Override
    public T visit(BinaryExpression arithmeticExpression) {
        Operator op = arithmeticExpression.getOperator();
        T left = visit(arithmeticExpression.getLeft());
        T right = visit(arithmeticExpression.getRight());
        return op.apply(left, right);
    }

    @Override
    public T visit(ConstantExpression expression) {
        return (T) expression.getValue();
    }
}

代表表达式的类

public abstract class Expression {

    public abstract  <T>  T accept(Visitor<T> visitor);
}

二进制表达式的类

public class BinaryExpression extends Expression {

    private Operator operator;
    private Expression left;
    private Expression right;

  //constructor and getters

    @Override public <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);
    }
}

代表常量值的类

public class ConstantExpression extends Expression {


    private Object value;

//constructor and getter

    @Override public <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);
    }
}

操作员分类

public abstract class Operator {

    public <T> T apply(T left, T right) {
        try {
            Method method = this.getClass().getMethod("do" + left.getClass().getSimpleName() + this.getClass().getSimpleName(), left.getClass(), right.getClass());
            method.setAccessible(true);
            return (T) method.invoke(this, left, right);
        } catch (NoSuchMethodException | InvocationTargetException | IllegalAccessException e) {
           throw new RuntimeException("Failed");
        }
    }
}

和加法运算符

public class Addition extends Operator {


    public Integer doIntegerAddition(Integer left, Integer right) {
        return left + right;
    }

    public Double doDoubleAddition(Double left, Double right) {
        return left + right;
    }

    public String doStringAddition(String left, String right) {
        return left + right;
    }
}

推荐答案

据我了解，您想解析一个文本表达式以生成可以多次评估的内容.

As I understand it, you want to parse a textual expression to produce something that you can evaluate multiple times.

当您获得您可以评估的东西"时，就应该仔细分析所解析的表达语言的细节，包括树结构，运算符的种类等.不要将这些顾虑推入公正的评估代码中.

By the time you get that "something you can evaluate", the details of the expression language you parsed, including the tree structure, the kinds of operators, etc., should all be taken care of. Don't push those concerns into the code the just needs to evaluate.

因此，您的解析过程应产生一个实现如下接口的对象:

So, your parsing process should produce an object that implements an interface something like this:

interface IExpression {
    double evaluateNumeric(Environment env);
    boolean evaluateLogical(Environment env);
    String evaluateString(Environment env);
    boolean isConstant();
}

在这里，Environment对象保存变量，函数定义等的值-表达式可以用作输入的任何内容.

Here, the Environment object holds the values of variables, function definitions, or whatever -- anything that expressions can use as input.

如您所见，该接口允许将任何表达式评估为布尔值(例如，如果在if中使用)，数字或字符串.根据您的表达语言，其中一些可能会抛出UnsupportedOperationException.例如，对于JavaScript之类的东西，它们几乎总是可以工作.

As you can see the interface allows any expression to be evaluated as a boolean (if used in an if, for example), as a number, or as a string. Depending on your expression language, some of these may throw UnsupportedOperationException. For something like JavaScript, for example, they would almost always all work.

您还可以使用一些方法来告诉您有关isConstant表达式的信息.根据语言的不同，提供表达式自然产生的对象的类型可能很重要.

You can also have methods that tell you things about the expression like isConstant. Depending on the language, it may be important to provide the type of object that the expression naturally produces.

为使操作实现问题脱离解析器，您可能需要为其提供一个工厂接口，如下所示:

To keep operation implementation concerns out of the parser, you may want to provide it with a factory interface like this:

IExpressionFactory {

    IExpression add(IExpression left, IExpression right);
    IExpression multiply(IExpression left, IExpression right);
    ///... etc. etc.
}

解析器将在此处为每个子表达式调用一个方法，以从其子表达式创建该方法.

The parser would call a method in here for each sub-expression, to create it from its children.

可以按您喜欢的任何方式实现不同类型的子表达式.在Java中，我通常为每个类别使用带有lambda参数的类，例如:

The different kinds of subexpression can be implemented any way you like. In Java, I usually use classes for each category with lambda arguments like:

class ExpressionFactory : IExpressionFactory {
    ...
    IExpression add(final IExpression left, final IExpression right) {
        return arithmeticBinary(left, right, (a,b)->a+b);
    }
    ...
}

这使您不必为每个运算符编写一个类.当我非常担心评估速度时，我将使用具有抽象基础的内联类.

That saves you from having to having to write a class for each operator. When I'm super concerned about evaluation speed, I'll use inline classes with abstract bases.

重要提示:请注意，由于编译后的IExpression不会公开为创建该表达式而解析的表达式树，因此您不必保留该结构，并且可以进行诸如常量折叠之类的优化:

IMPORTANT: Note that because a compiled IExpression doesn't expose the expression tree that was parsed to create it, you don't have to preserve that structure, and can do optimizations like constant folding:

IExpression arithmeticBinary(IExpression left, IExpression right, DoubleBiFunc operator) {
    if (left.isConstant() && right.isConstant()) {
        // The operands are constant, so we can evaluate this during compilation
        double value = operator.apply(
            left.evaluateNumeric(EMPTY_ENV),
            right.evaluateNumeric(EMPTY_ENV));
        return new NumericConstant(value);
    } else {
        return new ArithmeticBinaryExpression(left, right, operator);
    }
}

通过在编译期间进行尽可能多的处理，可以摆脱所有类型/转换检查并执行各种优化，从而加快评估速度.

By processing as much as possible during compilation, you can make evaluation faster, by getting rid of all type/conversion checks, and performing various optimizations.

这篇关于使用访问者模式的表情评估的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！