使用变量评估数学表达式。 (java 8)

Question

我需要更多帮助来回答这个问题，Evaluating a math expression given in string form。用户@Boann 用一个非常有趣的算法回答了这个问题，他还指出可以更改该算法以接受变量。我已经设法改变它并让它工作，但不知道他是如何区分编译和求值的。这是我的代码：

import java.util.HashMap;
import java.util.Map;

public class EvaluateExpressionWithVariabels {

@FunctionalInterface
interface Expression {
    double eval();
}

public static void main(String[] args){
    Map<String,Double> variables = new HashMap<>();     
    for (double x = 100; x <= +120; x++) {
        variables.put("x", x);
        System.out.println(x + " => " + eval("x+(sqrt(x))",variables).eval());
    }
}

public static Expression eval(final String str,Map<String,Double> variables) {
    return new Object() {
        int pos = -1, ch;

        //if check pos+1 is smaller than string length ch is char at new pos
        void nextChar() {
            ch = (++pos < str.length()) ? str.charAt(pos) : -1;
        }

        //skips 'spaces' and if current char is what was searched, if true move to next char return true
        //else return false
        boolean eat(int charToEat) {
            while (ch == ' ') nextChar();
            if (ch == charToEat) {
                nextChar();
                return true;
            }
            return false;
        }


        Expression parse() {
            nextChar();
            Expression x = parseExpression();
            if (pos < str.length()) throw new RuntimeException("Unexpected: " + (char)ch);
            return x;
        }

        // Grammar:
        // expression = term | expression `+` term | expression `-` term
        // term = factor | term `*` factor | term `/` factor
        // factor = `+` factor | `-` factor | `(` expression `)`
        //        | number | functionName factor | factor `^` factor

        Expression parseExpression() {
            Expression x = parseTerm();
            for (;;) {
                if (eat('+')) { // addition
                    Expression a = x, b = parseTerm();                      
                    x = (() -> a.eval() + b.eval());
                } else if (eat('-')) { // subtraction
                    Expression a = x, b = parseTerm();
                    x = (() -> a.eval() - b.eval());
                } else {
                    return x;
                }
            }
        }

        Expression parseTerm() {
            Expression x = parseFactor();
            for (;;) {
                if (eat('*')){
                     Expression a = x, b = parseFactor(); // multiplication
                     x = (() -> a.eval() * b.eval());
                }
                else if(eat('/')){
                     Expression a = x, b = parseFactor(); // division
                     x = (() -> a.eval() / b.eval());
                }
                else return x;
            }
        }

        Expression parseFactor() {
            if (eat('+')) return parseFactor(); // unary plus
            if (eat('-')){
                Expression b = parseFactor(); // unary minus
                return (() -> -1 * b.eval());
            }

            Expression x;
            int startPos = this.pos;
            if (eat('(')) { // parentheses
                x = parseExpression();
                eat(')');
            } else if ((ch >= '0' && ch <= '9') || ch == '.') { // numbers
                while ((ch >= '0' && ch <= '9') || ch == '.'){                     
                    nextChar();
                }
                double xx = Double.parseDouble(str.substring(startPos, this.pos));
                x = () -> xx;
            } else if (ch >= 'a' && ch <= 'z') { // functions
                while (ch >= 'a' && ch <= 'z') nextChar();
                String func = str.substring(startPos, this.pos);

                if ( variables.containsKey(func)){
                    x = () -> variables.get(func);
                }else{
                    double xx = parseFactor().eval();
                    if (func.equals("sqrt")) x = () -> Math.sqrt(xx);
                    else if (func.equals("sin")) x = () -> Math.sin(Math.toRadians(xx));
                    else if (func.equals("cos")) x = () -> Math.cos(Math.toRadians(xx));
                    else if (func.equals("tan")) x = () -> Math.tan(Math.toRadians(xx));                    
                    else throw new RuntimeException("Unknown function: " + func);
                }
            } else {
                throw new RuntimeException("Unexpected: " + (char)ch);
            }

            if (eat('^')){ 
                x = () -> {
                    double d =  parseFactor().eval();
                    return Math.pow(d,d); // exponentiation
                };
            }

            return  x;
        }
    }.parse();
}
}

如果你看一下他的主要回答

public static void main(String[] args) {
    Map<String,Double> variables = new HashMap<>();
    Expression exp = parse("x^2 - x + 2", variables);
    for (double x = -20; x <= +20; x++) {
        variables.put("x", x);
        System.out.println(x + " => " + exp.eval());
    }
}

他在这一行 Expression exp = parse("x^2 - x + 2", variables); 上调用函数 parse 来编译表达式一次，并使用 for 使用唯一的 x 值对其求值多次。 parse函数指的是什么。

ps: 我评论了网友的问题没有回复

Answer 1

我认为包含地图参考的 Expression 的实际代码并未在答案中发布。

为了使该示例代码起作用，表达式必须具有某种内存。实际上，代码操纵了映射，并且由于表达式持有对它的引用，因此对表达式的 eval 方法的每次后续调用都将采用调整后的值。

因此，为了让代码正常工作，您首先需要一个表达式实现，它包含一个地图引用。但要注意这样的表达式可能产生的任何副作用。

所以对于那个特定的例子，代码必须像下面这样（没有时间完全看它是否有效，但你会明白的：重要的是，表达式包含一个从外部更改的参考）：

static Expression parse(String expression, Map<String, String> variables) {
    return new PseudoCompiledExpression(expression, variables);
}
static class PseudoCompiledExpression implements Expression {
    Map<String, String> variables;
    Expression wrappedExpression;
    PseudoCompiledExpression(String expression, Map<String, String> variables) {
       this.variables = variables;
       wrappedExpression = eval(expression, variables);
    }
   public double eval() {
        // the state of the used map is altered from outside... 
        return wrappedException.eval();
   }

Answer 2

抱歉造成混淆。我提到的“parse”函数只是现有的 eval 函数，但由于它 returns 一个 Expression 对象而重命名。

所以你有：

public static Expression parse(String str, Map<String,Double> variables) { ... }

并通过以下方式调用它：

Map<String,Double> variables = new HashMap<>();
Expression exp = parse("x+(sqrt(x))", variables);
for (double x = 100; x <= +120; x++) {
    variables.put("x", x);
    System.out.println(x + " => " + exp.eval());
}

另一件事：有必要在解析时知道名称是指变量还是函数，以便知道它是否需要参数，但你不能调用 containsKey在解析期间在变量映射上，因为在调用 exp.eval() 之前变量可能不会出现在映射中！一种解决方案是将函数放在映射中，这样您就可以调用 containsKey：

    } else if (ch >= 'a' && ch <= 'z') { // functions and variables
        while (ch >= 'a' && ch <= 'z') nextChar();
        String name = str.substring(startPos, this.pos);
        if (functions.containsKey(name)) {
            DoubleUnaryOperator func = functions.get(name);
            Expression arg = parseFactor();
            x = () -> func.applyAsDouble(arg.eval());
        } else {
            x = () -> variables.get(name);
        }
    } else {

然后在 class 级别的某处，初始化 functions 地图：

private static final Map<String,DoubleUnaryOperator> functions = new HashMap<>();
static {
    functions.put("sqrt", x -> Math.sqrt(x));
    functions.put("sin", x -> Math.sin(Math.toRadians(x)));
    functions.put("cos", x -> Math.cos(Math.toRadians(x)));
    functions.put("tan", x -> Math.tan(Math.toRadians(x)));
}

（也可以将 functions 映射定义为解析器内部的局部变量，但这会在每次解析期间增加一点开销。）

Answer 3

我发现上面的语法不适用于取幂。这个有效：

public class BcInterpreter {

static final String BC_SPLITTER = "[\^\(\/\*\-\+\)]";
static Map<String,Double> variables = new HashMap<>();
private static final Map<String,DoubleUnaryOperator> functions = new HashMap<>();

static {
    functions.put("sqrt", x -> Math.sqrt(x));
    functions.put("sin", x -> Math.sin(Math.toRadians(x)));
    functions.put("cos", x -> Math.cos(Math.toRadians(x)));
    functions.put("tan", x -> Math.tan(Math.toRadians(x)));
    functions.put("round", x -> Math.round(x));
    functions.put("abs", x -> Math.abs(x));
    functions.put("ceil", x -> Math.ceil(x));
    functions.put("floor", x -> Math.floor(x));
    functions.put("log", x -> Math.log(x));
    functions.put("exp", x -> Math.exp(x));
    // TODO: add more unary functions here.
}

/**
 * Parse the expression into a lambda, and evaluate with the variables set from fields
 * in the current row.  The expression only needs to be evaluated one time.
 * @param recordMap
 * @param fd
 * @param script
 * @return
 */
static String materialize(Map<String, String> recordMap, FieldDesc fd, String script){
    // parse the expression one time and save the lambda in the field's metadata
    if (fd.get("exp") == null) {
        fd.put("exp", parse(script, variables));
    }
    // set the variables to be used with the expression, once per row
    String[] tokens = script.split(BC_SPLITTER);
    for(String key : tokens) {
        if (key != null) {
            String val = recordMap.get(key.trim());
            if (val != null)
                variables.put(key.trim(), Double.parseDouble(val));
        }
    }
    // evaluate the expression with current row's variables
    return String.valueOf(((Expression)(fd.get("exp"))).eval());
}

@FunctionalInterface
interface Expression {
    double eval();
}

static Map<String,Double> getVariables(){
    return variables;
}

public static Expression parse(final String str,Map<String,Double> variables) {
    return new Object() {
        int pos = -1, ch;

        //if check pos+1 is smaller than string length ch is char at new pos
        void nextChar() {
            ch = (++pos < str.length()) ? str.charAt(pos) : -1;
        }

        //skips 'spaces' and if current char is what was searched, if true move to next char return true
        //else return false
        boolean eat(int charToEat) {
            while (ch == ' ') nextChar();
            if (ch == charToEat) {
                nextChar();
                return true;
            }
            return false;
        }

        Expression parse() {
            nextChar();
            Expression x = parseExpression();
            if (pos < str.length()) throw new RuntimeException("Unexpected: " + (char)ch);
            return x;
        }

        // Grammar:
        // expression = term | expression `+` term | expression `-` term
        // term = factor | term `*` factor | term `/` factor
        // factor = base | base '^' base
        // base = '-' base | '+' base | number | identifier | function factor | '(' expression ')'

        Expression parseExpression() {
            Expression x = parseTerm();
            for (;;) {
                if (eat('+')) { // addition
                    Expression a = x, b = parseTerm();
                    x = (() -> a.eval() + b.eval());
                } else if (eat('-')) { // subtraction
                    Expression a = x, b = parseTerm();
                    x = (() -> a.eval() - b.eval());
                } else {
                    return x;
                }
            }
        }

        Expression parseTerm() {
            Expression x = parseFactor();
            for (;;) {
                if (eat('*')){
                    Expression a = x, b = parseFactor(); // multiplication
                    x = (() -> a.eval() * b.eval());
                } else if(eat('/')){
                    Expression a = x, b = parseFactor(); // division
                    x = (() -> a.eval() / b.eval());
                } else {
                    return x;
                }
            }
        }

        Expression parseFactor(){
            Expression x = parseBase();
            for(;;){
                if (eat('^')){
                    Expression a = x, b = parseBase();
                    x = (()->Math.pow(a.eval(),b.eval()));
                }else{
                    return x;
                }
            }
        }
        Expression parseBase(){
            int startPos = this.pos;
            Expression x;
            if (eat('-')){
                Expression b = parseBase();
                x = (()-> (-1)*b.eval());
                return x;
            }else if (eat('+')){
                x = parseBase();
                return x;
            }
            if (eat('(')) { // parentheses
                x = parseExpression();
                eat(')');
                return x;
            } else if ((ch >= '0' && ch <= '9') || ch == '.') { // numbers
                while ((ch >= '0' && ch <= '9') || ch == '.'){
                    nextChar();
                }
                double xx = Double.parseDouble(str.substring(startPos, this.pos));
                x = () -> xx;
                return x;
            } else if (ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z') { // functions and variables
                while (ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z') nextChar();
                String name = str.substring(startPos, this.pos);
                if (functions.containsKey(name)) {
                    DoubleUnaryOperator func = functions.get(name);
                    Expression arg = parseFactor();
                    x = () -> func.applyAsDouble(arg.eval());
                } else {
                    x = () -> variables.get(name);
                }
                return x;
            }else {
                throw new RuntimeException("Unexpected: " + (char)ch);
            }
        }
    }.parse();
}
}

使用变量评估数学表达式。 (java 8)

Evaluating a math expression with variables. (java 8)

java

recursive-descent

abstract-syntax-tree