Java: разделить Список на два подсписка?

Я написал этот метод 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 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();
                eat(')');
            } 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);
                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, например Map variables.
• Отдельная компиляция и оценка: что, если, добавив поддержку переменных, вы хотели бы оценить одно и то же выражение миллионы раз с измененными переменными, без разбора его каждый раз? Возможно. Сначала определите интерфейс, который будет использоваться для оценки прекомпилированного выражения:

  @FunctionalInterface
  interface Expression {
      double eval();
  }
  

  Теперь измените все методы, возвращающие double s, поэтому вместо этого они возвращают экземпляр этого интерфейса. Синтаксис лямбды 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 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, позволяя смешивать типы данных в выражениях, как и в реальном языке программирования. :)

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