使用变量进行数学表达式求值（Java 8）

Question

我需要关于这个问题的额外帮助：如何计算以字符串形式给出的数学表达式。用户@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());
    }
}

他在这一行上调用函数parse： Expression exp = parse("x^2 - x + 2", variables);，以便编译一次表达式，并使用for循环评估多个具有唯一x值的表达式。 parse函数是什么意思。

注：我已经评论了用户的问题但没有得到回复。

- Hozeis

---

“parse” 函数是什么意思？Expression parse() { nextChar(); Expression x = parseExpression(); if (pos < str.length()) throw new RuntimeException("Unexpected: " + (char)ch); return x; } - Thibstars

我不相信那是正确的，因为该函数对于主函数不可见，而他调用的“parse”函数需要两个参数。@Thibstars - Hozeis

你是对的。应该是 eval() 吧？ - Thibstars

如果调用 eval() 而不是解析它，它会尝试解决方程，如果 variables 不包含 x，则会出现错误。@Thibstars - Hozeis

我认为其他问题的示例代码已经过了一些重构，因为变量是在初始化Expression之后放置的，这意味着表达式拥有某种记忆，但现在不再具备。因此，您只需要在循环内调用eval(String, Map)即可，之前的parse不再需要。 - Roland

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

- Roland

---

谢谢你的帮助，但 Boann 已经澄清了他的答案。 - Hozeis

Answer 2

对于之前的混淆，我所提到的“parse”函数实际上就是现有的eval函数，只是改名了，因为它返回一个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 {

然后在类级别的某个地方，初始化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映射定义为解析器内的局部变量也可以，但在每次解析时会增加一些额外开销。

- Boann

---

非常感谢。这个选项比使用JavaScript快得多。 - Hozeis

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

- mike scholtes

---

你好，我刚刚测试了负指数，它们似乎不能正常工作，但正指数可以。虽然我不需要它，但知道这一点还是很好的。谢谢。 - Hozeis

"表达式 arg = parseFactor();" 最好将 args 解析为一个完整的表达式，如 "Expression arg = parseExpression();" 然后再使用 eat(')'); 函数。 - Sarthak_ssg5