How to evaluate a math expression given in string form?

Я пытаюсь написать Java-процедуру для вычисления математических выражений из String значений типа:

1. "5+3"


2. "10-4*5"


3. "(1+10)*3"

Я хочу избежать множества операторов if-then-else . Как я могу это сделать?

С JDK1.6 вы можете использовать встроенный движок Javascript.

import javax.script.ScriptEngineManager;
import javax.script.ScriptEngine;
import javax.script.ScriptException;

public class Test {
  public static void main(String[] args) throws ScriptException {
    ScriptEngineManager mgr = new ScriptEngineManager();
    ScriptEngine engine = mgr.getEngineByName("JavaScript");
    String foo = "40+2";
    System.out.println(engine.eval(foo));
    } 
}

Я написал этот eval метод для арифметических выражений, чтобы ответить на этот вопрос. Он выполняет сложение, вычитание, умножение, деление, возведение в степень (используя ^ символ) и несколько базовых функций, таких как sqrt. Он поддерживает группировку с использованием (...), и он получает правильные правила приоритета операторов и ассоциативности.

public static double eval(final String str) {
    return new Object() {
        int pos = -1, ch;
        
        void nextChar() {
            ch = (++pos < str.length()) ? str.charAt(pos) : -1;
        }
        
        boolean eat(int charToEat) {
            while (ch == ' ') nextChar();
            if (ch == charToEat) {
                nextChar();
                return true;
            }
            return false;
        }
        
        double parse() {
            nextChar();
            double 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 `(` expression `)` | functionName factor
        //        | factor `^` factor
        
        double parseExpression() {
            double x = parseTerm();
            for (;;) {
                if      (eat('+')) x += parseTerm(); // addition
                else if (eat('-')) x -= parseTerm(); // subtraction
                else return x;
            }
        }
        
        double parseTerm() {
            double x = parseFactor();
            for (;;) {
                if      (eat('*')) x *= parseFactor(); // multiplication
                else if (eat('/')) x /= parseFactor(); // division
                else return x;
            }
        }
        
        double parseFactor() {
            if (eat('+')) return +parseFactor(); // unary plus
            if (eat('-')) return -parseFactor(); // unary minus
            
            double x;
            int startPos = this.pos;
            if (eat('(')) { // parentheses
                x = parseExpression();
                if (!eat(')')) throw new RuntimeException("Missing ')'");
            } else if ((ch >= '0' && ch <= '9') || ch == '.') { // numbers
                while ((ch >= '0' && ch <= '9') || ch == '.') nextChar();
                x = Double.parseDouble(str.substring(startPos, this.pos));
            } else if (ch >= 'a' && ch <= 'z') { // functions
                while (ch >= 'a' && ch <= 'z') nextChar();
                String func = str.substring(startPos, this.pos);
                if (eat('(')) {
                    x = parseExpression();
                    if (!eat(')')) throw new RuntimeException("Missing ')' after argument to " + func);
                } else {
                    x = parseFactor();
                }
                if (func.equals("sqrt")) x = Math.sqrt(x);
                else if (func.equals("sin")) x = Math.sin(Math.toRadians(x));
                else if (func.equals("cos")) x = Math.cos(Math.toRadians(x));
                else if (func.equals("tan")) x = Math.tan(Math.toRadians(x));
                else throw new RuntimeException("Unknown function: " + func);
            } else {
                throw new RuntimeException("Unexpected: " + (char)ch);
            }
            
            if (eat('^')) x = Math.pow(x, parseFactor()); // exponentiation
            
            return x;
        }
    }.parse();
}

Пример:

System.out.println(eval("((4 - 2^3 + 1) * -sqrt(3*3+4*4)) / 2"));

Результат: 7.5 (который правильный)

Анализатор является анализатором рекурсивного спуска, поэтому внутренне использует отдельные методы синтаксического анализа для каждого уровня приоритета операторов в своей грамматике. Я намеренно сохранил его коротким, но вот несколько идей, которыми вы, возможно, захотите дополнить его:

• Переменные:

  
  

  Бит синтаксического анализатора, считывающий имена функций, можно легко изменить и для обработки пользовательских переменных, выполнив поиск имен в таблице переменных, переданной методу eval, например, a Map<String,Double> variables.

  
  



• Отдельная компиляция и вычисление:

  
  

  Что, если, добавив поддержку переменных, вы захотите вычислять одно и то же выражение миллионы раз с измененными переменными, не разбирая его каждый раз? Это возможно. Сначала определите интерфейс, который будет использоваться для вычисления предварительно скомпилированного выражения:

  
  

    @FunctionalInterface
    interface Expression {
        double eval();
    }
  

  
  

  Теперь, чтобы переработать исходную функцию "eval" в функцию "parse", измените все методы, которые возвращают doubles, чтобы вместо этого они возвращали экземпляр этого интерфейса. Для этого хорошо подходит лямбда-синтаксис Java 8. Пример одного из измененных методов:

  
  

    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 объектов, представляющих скомпилированное выражение (абстрактное синтаксическое дерево). Затем вы можете скомпилировать его один раз и повторно вычислять с разными значениями.:

  
  

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

  
  



• Разные типы данных:

  
  

  Вместо double вы могли бы изменить вычислитель, чтобы использовать что-то более мощное, например BigDecimal, или класс, который реализует комплексные числа или рациональные числа (дроби). Вы могли бы даже использовать Object, допуская некоторое сочетание типов данных в выражениях, как в реальном языке программирования. :)

  
  

_{Весь код в этом ответе опубликован в общественном достоянии. Получайте удовольствие!}

Для моего университетского проекта я искал анализатор / вычислитель, поддерживающий как базовые формулы, так и более сложные уравнения (особенно повторяющиеся операторы). Я нашел очень хорошую библиотеку с открытым исходным кодом для JAVA и .NET под названием mXparser. Я приведу несколько примеров, чтобы составить некоторое представление о синтаксисе, для получения дальнейших инструкций, пожалуйста, посетите веб-сайт проекта (особенно раздел "Руководство").

https://mathparser.org/

https://mathparser.org/mxparser-tutorial/

https://mathparser.org/api/

И несколько примеров

1 - Простая фурмула

Expression e = new Expression("( 2 + 3/4 + sin(pi) )/2");
double v = e.calculate()

2 - Пользовательские аргументы и константы

Argument x = new Argument("x = 10");
Constant a = new Constant("a = pi^2");
Expression e = new Expression("cos(a*x)", x, a);
double v = e.calculate()

3 - Определяемые пользователем функции

Function f = new Function("f(x, y, z) = sin(x) + cos(y*z)");
Expression e = new Expression("f(3,2,5)", f);
double v = e.calculate()

4 итерации

Expression e = new Expression("sum( i, 1, 100, sin(i) )");
double v = e.calculate()

Найдено недавно - на случай, если вы хотите попробовать синтаксис (и посмотреть расширенный вариант использования), вы можете загрузить приложение для скалярногокалькулятора, работающее на базе mXparser.

Правильный способ решить эту проблему - использовать лексер и синтаксический анализатор. Вы можете написать простые версии этих выражений самостоятельно, или на этих страницах также есть ссылки на Java-лексеры и синтаксические анализаторы.

Создание анализатора рекурсивного спуска - действительно хорошее учебное упражнение.