Разбор и вычисление значения математического выражения

 
 
 
Сообщения:1184
На прошлой неделе прислали ТЗ на создание Отчета по капитальным инвестициям. В нем было требование настраивать строки и столбцы через скрипт на Jyton'e.
Настройка строк сводилась к перечислению групп объектов, операции которых должны были участвовать в вычислении значения строки. Со столбцами ситуация обстояла сложнее - здесь нужно было задать правила вычисления.
Т. к. значения по столбцам должны были вычисляться на основании полей операций, значений по другим столбцам, а также могли умножаться и делиться на число, я решил сделать правило столбца в виде обычного математического выражения типа String. Естественно, встала проблема разбора выражения и вычисления его значения.
В этом топике хотелось бы поделиться опытом приведения выражения к Обратной польской нотации и вычисления результата на ее основании.

Теория с примерами достаточно неплохо изложена в Википедии. Неплохая английская статья с анимацией работы алгоритма лежит здесь.

Здесь я отброшу специфику моей задачи и приведу свою реализацию описанных алгоритмов для разбора выражения, содержащего числа с плавающей точкой, четыре основных математических операнда и скобки.
import java.math.BigDecimal;
import java.util.*;

/**
 * Класс содержит утилиты для разбора и обработки математических выражений.
 *
 * @author Борис Марченко
 * @version $Revision$ $Date$
 */
public class ExpressionUtils {
    /**
     * Основные математические операции и их приоритеты.
     *
     * @see #sortingStation(String, java.util.Map)
     */
    public static final Map<String, Integer> MAIN_MATH_OPERATIONS;

    static {
        MAIN_MATH_OPERATIONS = new HashMap<String, Integer>();
        MAIN_MATH_OPERATIONS.put("*", 1);
        MAIN_MATH_OPERATIONS.put("/", 1);
        MAIN_MATH_OPERATIONS.put("+", 2);
        MAIN_MATH_OPERATIONS.put("-", 2);
    }

    /**
     * Преобразует выражение из инфиксной нотации в обратную польскую нотацию (ОПН) по алгоритму <i>Сортировочная
     * станция</i> Эдскера Дейкстры. Отличительной особенностью обратной польской нотации является то, что все
     * аргументы (или операнды) расположены перед операцией. Это позволяет избавиться от необходимости использования
     * скобок. Например, выражение, записаное в инфиксной нотации как 3 * (4 + 7), будет выглядеть как 3 4 7 + *
     * в ОПН. Символы скобок могут быть изменены.
     * <a href="http://ru.wikipedia.org/wiki/Обратная_польская_запись">Подробнее об ОПЗ</a>.
     *
     * @param expression выражение в инфиксной форме.
     * @param operations операторы, использующиеся в выражении (ассоциированные, либо лево-ассоциированные).
     * Значениями карты служат приоритеты операции (самый высокий приоритет - 1). Например, для 5
     * основных математических операторов карта будет выглядеть так:
     * <pre>
     *      *   ->   1
     *      /   ->   1
     *      +   ->   2
     *      -   ->   2
     * </pre>
     * Приведенные операторы определены в константе {@link #MAIN_MATH_OPERATIONS}.
     * @param leftBracket открывающая скобка.
     * @param rightBracket закрывающая скобка.
     * @return преобразованное выражение в ОПН.
     */
    public static String sortingStation(String expression, Map<String, Integer> operations, String leftBracket,
                                        String rightBracket) {
        if (expression == null || expression.length() == 0)
            throw new IllegalStateException("Expression isn't specified.");
        if (operations == null || operations.isEmpty())
            throw new IllegalStateException("Operations aren't specified.");
        // Выходная строка, разбитая на "символы" - операции и операнды..
        List<String> out = new ArrayList<String>();
        // Стек операций.
        Stack<String> stack = new Stack<String>();

        // Удаление пробелов из выражения.
        expression = expression.replace(" ", "");

        // Множество "символов", не являющихся операндами (операции и скобки).
        Set<String> operationSymbols = new HashSet<String>(operations.keySet());
        operationSymbols.add(leftBracket);
        operationSymbols.add(rightBracket);

        // Индекс, на котором закончился разбор строки на прошлой итерации.
        int index = 0;
        // Признак необходимости поиска следующего элемента.
        boolean findNext = true;
        while (findNext) {
            int nextOperationIndex = expression.length();
            String nextOperation = "";
            // Поиск следующего оператора или скобки.
            for (String operation : operationSymbols) {
                int i = expression.indexOf(operation, index);
                if (i >= 0 && i < nextOperationIndex) {
                    nextOperation = operation;
                    nextOperationIndex = i;
                }
            }
            // Оператор не найден.
            if (nextOperationIndex == expression.length()) {
                findNext = false;
            } else {
                // Если оператору или скобке предшествует операнд, добавляем его в выходную строку.
                if (index != nextOperationIndex) {
                    out.add(expression.substring(index, nextOperationIndex));
                }
                // Обработка операторов и скобок.
                // Открывающая скобка.
                if (nextOperation.equals(leftBracket)) {
                    stack.push(nextOperation);
                }
                // Закрывающая скобка.
                else if (nextOperation.equals(rightBracket)) {
                    while (!stack.peek().equals(leftBracket)) {
                        out.add(stack.pop());
                        if (stack.empty()) {
                            throw new IllegalArgumentException("Unmatched brackets");
                        }
                    }
                    stack.pop();
                }
                // Операция.
                else {
                    while (!stack.empty() && !stack.peek().equals(leftBracket) &&
                            (operations.get(nextOperation) >= operations.get(stack.peek()))) {
                        out.add(stack.pop());
                    }
                    stack.push(nextOperation);
                }
                index = nextOperationIndex + nextOperation.length();
            }
        }
        // Добавление в выходную строку операндов после последнего операнда.
        if (index != expression.length()) {
            out.add(expression.substring(index));
        }
        // Пробразование выходного списка к выходной строке.
        while (!stack.empty()) {
            out.add(stack.pop());
        }
        StringBuffer result = new StringBuffer();
        if (!out.isEmpty())
            result.append(out.remove(0));
        while (!out.isEmpty())
            result.append(" ").append(out.remove(0));

        return result.toString();
    }

    /**
     * Преобразует выражение из инфиксной нотации в обратную польскую нотацию (ОПН) по алгоритму <i>Сортировочная
     * станция</i> Эдскера Дейкстры. Отличительной особенностью обратной польской нотации является то, что все
     * аргументы (или операнды) расположены перед операцией. Это позволяет избавиться от необходимости использования
     * скобок. Например, выражение, записаное в инфиксной нотации как 3 * (4 + 7), будет выглядеть как 3 4 7 + *
     * в ОПН.
     * <a href="http://ru.wikipedia.org/wiki/Обратная_польская_запись">Подробнее об ОПЗ</a>.
     *
     * @param expression выражение в инфиксной форме.
     * @param operations операторы, использующиеся в выражении (ассоциированные, либо лево-ассоциированные).
     * Значениями карты служат приоритеты операции (самый высокий приоритет - 1). Например, для 5
     * основных математических операторов карта будет выглядеть так:
     * <pre>
     *      *   ->   1
     *      /   ->   1
     *      +   ->   2
     *      -   ->   2
     * </pre>
     * Приведенные операторы определены в константе {@link #MAIN_MATH_OPERATIONS}.
     * @return преобразованное выражение в ОПН.
     */
    public static String sortingStation(String expression, Map<String, Integer> operations) {
        return sortingStation(expression, operations, "(", ")");
    }

    /**
     * Вычисляет значение выражения, записанного в инфиксной нотации. Выражение может содержать скобки, числа с
     * плавающей точкой, четыре основных математических операндов.
     *
     * @param expression выражение.
     * @return результат вычисления.
     */
    public static BigDecimal calculateExpression(String expression) {
        String rpn = sortingStation(expression, MAIN_MATH_OPERATIONS);
        StringTokenizer tokenizer = new StringTokenizer(rpn, " ");
        Stack<BigDecimal> stack = new Stack<BigDecimal>();
        while (tokenizer.hasMoreTokens()) {
            String token = tokenizer.nextToken();
            // Операнд.
            if (!MAIN_MATH_OPERATIONS.keySet().contains(token)) {
                stack.push(new BigDecimal(token));
            } else {
                BigDecimal operand2 = stack.pop();
                BigDecimal operand1 = stack.empty() ? BigDecimal.ZERO : stack.pop();
                if (token.equals("*")) {
                    stack.push(operand1.multiply(operand2));
                } else if (token.equals("/")) {
                    stack.push(operand1.divide(operand2));
                } else if (token.equals("+")) {
                    stack.push(operand1.add(operand2));
                } else if (token.equals("-")) {
                    stack.push(operand1.subtract(operand2));
                }
            }
        }
        if (stack.size() != 1)
            throw new IllegalArgumentException("Expression syntax error.");
        return stack.pop();
    }

    /**
     * Закрытый конструктор класса.
     */
    private ExpressionUtils() {
    }

    /**
     * Тестирует методы.
     *
     * @param args список аргументов командной строки.
     */
    public static void main(String[] args) {
        String expression = "3 + 4 * 2 / (1 - 5) + 2";
        System.out.println("Инфиксная нотация:         " + expression);
        System.out.println("\tРезультат 3");
        String rpn = sortingStation(expression, MAIN_MATH_OPERATIONS);
        System.out.println("Обратная польская нотация: " + rpn);
        System.out.println("\tРезультат " + calculateExpression(expression));
    }
}

/*
$Log: $
*/


Результат:
Инфиксная нотация: 3 + 4 * 2 / (1 - 5) + 2
	Результат 3
Обратная польская нотация: 3 4 2 * 1 5 - / + 2 +
	Результат 3

Не знала Настя, где зад, где перёд. Показали - разобралась.
 
 
Сообщения:595
"Красивый" код =)

While (!Life.EOF) {
You.Money++;
You.Girls.Add(new Girl(90,60,90));
BeHappy();
}
 
 
Сообщения:1184
А что Вас смущает? Всегда готов выслушать замечания и предложния. ;)

Не знала Настя, где зад, где перёд. Показали - разобралась.
 
 
Сообщения:595
Marbo:
А что Вас смущает? Всегда готов выслушать замечания и предложния. ;)


Нее... я хотел сказать что действительно хорош. =)

While (!Life.EOF) {
You.Money++;
You.Girls.Add(new Girl(90,60,90));
BeHappy();
}
 
 
Сообщения:1184
А, спасибо ))

Не знала Настя, где зад, где перёд. Показали - разобралась.
 
 
Сообщения:10026
Я сначала не уделил внимания, но теперь присмотрелся. :) Мне когда-то нужно было тоже собирать из строки мат. выражения, только совсем в упрощенной форме(времени убил немало). Но это воистину шедевр :wink:
Если не секрет, сколько потратил времени на написание?
 
 
Сообщения:1184
На то, что привел здесь - полдня. Еще полтора на то, чтобы затесать алгоритм под свои нужды. Алгоритм достаточно простой и хорошо изложен. Сначала собирался делать с помощью пакета javacc, по потом коллега посоветовал посмотреть ОПН. Для простых задач, где положение оператора/операнда не влияет на его смысловую нагрузку, это - оптимальное решение.

Не знала Настя, где зад, где перёд. Показали - разобралась.
 
 
Сообщения:1460
Только мне вот что не понятно...
Jython вроде как поддерживает lambda-выражения и замыкания. Тогда зачем работать с выражениями как со строками?
Хотя я могу и ошибаться.
 
 
Сообщения:1184
Дело в том, что в скрипт мне нужно было вынести только тот минимум, который требовался бы ИТ-шникам клиента для настройки отчета. Он должен был представлять собой настроечный интерфейс, а не логику. Поэтому в скрипт я вынес только самое необходимое. Необходимое представляло собой, как я уже говорил, объект настройки с двумя методами, опеределяющими правила строк и столбцов.
Настройка столбцов производилась через выражения такого вида:
wrapper.addColumnRule(1, '{VEA_INPUT:startBalCost:flag>1} + {VEA_OUT:startBalCost} - {VEA_OUT:crntBalCost}')

После разбора выражения для каждой операции производится проверка.
Для первого столбца:
ЕСЛИ Операция.тип=VEA_INPUT
    ЕСЛИ Поле_операции.flag > 1
        добавить к ячейке 1 столбца значение Поле_операции.startBalCost
ЕСЛИ Операция.тип=VEA_INPUT
    добавить к ячейке 1 столбца разности Поле_операции.startBalCost и Поле_операции.crntBalCost            

В формулах было до 15 переменных-полей операций, кроме того должны были присутствовать ссылки на другие столбцы отчета. Расписывая все это в виде if-else'ов, мы бы получили кучу непонятного конечному пользователя кода, в котором бы использовались неизвестные ему методы доступа к данным.

Не знала Настя, где зад, где перёд. Показали - разобралась.
 
 
Сообщения:14
В качестве иллюстрации функционального подхода к решению задачи приведу реализацию на языке Scala:

import util.parsing.combinator.lexical.StdLexical
import util.parsing.combinator.syntactical.StdTokenParsers

object ArithmeticParser extends StdTokenParsers {
  type Tokens = StdLexical
  val lexical = new StdLexical
  lexical.delimiters ++= List("(", ")", "+", "-", "*", "/")

  def expr = term*("+" ^^^ {(x: Int, y: Int) => x + y}
                 | "-" ^^^ {(x: Int, y: Int) => x - y})
  def term = factor*("*" ^^^ {(x: Int, y: Int) => x * y}
                   | "/" ^^^ {(x: Int, y: Int) => x / y})
  def factor: Parser[Int] = "(" ~> expr <~ ")" | numericLit ^^ (_.toInt)

  def main(args: Array[String]) =
    if (args.length >= 1)
      println(expr(new lexical.Scanner(args(0))))
}


Пример вычислений:

Z:\>scala ArithmeticParser "3 + 4 * 2 / (1 - 5) + 2"
[1.24] parsed: 3
Z:\>scala ArithmeticParser "8 + (5 * (3 + 4 + 1 - (6 - (4 / 2)) - 4))"
[1.26] parsed: 8


Преимущества подхода традиционные для функционального программирования:

* Лаконичность кода при сохранении удобочитаемости;
* Декларативная запись алгоритма;
* Высокий потенциал к повторному использованию кода и расширению функциональности.

Недостатки также традиционные:

* Более низкая производительность в сравнении с императивным решением.

P.S. Для тестирования кода использовалась версия Scala 2.8b1, но, судя по всему, все должно работать без изменений и в Scala 2.7.7.
 
 
Сообщения:2441
Nikolaich:

* Лаконичность кода при сохранении удобочитаемости;

Это была шутка?
 
 
Сообщения:5
а можно прояснить такие моменты:
public Map<String, Integer> MAIN_MATH_OPERATIONS;

    {
        MAIN_MATH_OPERATIONS = new HashMap<String, Integer>();
        MAIN_MATH_OPERATIONS.put("*", 1);
        MAIN_MATH_OPERATIONS.put("/", 1);
        MAIN_MATH_OPERATIONS.put("+", 2);
        MAIN_MATH_OPERATIONS.put("-", 2);
    }

что это за структура данных? где почитать про нее?

List<String> out = new ArrayList<String>() - это коллекции, или я не прав? опять же, где почитать?
Set<String> operationSymbols = new HashSet<String>(operations.keySet()) - даже догадок нету
for (String operation : operationSymbols) - тоже не понятно

Information must be free!
 
 
Сообщения:2
Подскажите в плане операций с одним аргументом. К примеру если я ещё хочу реализовать тригонометрические функции типа cos(x) то как поступить в ОПН?
 
 
Сообщения:791
Такие задачи правильнее решать с помощью конечных автоматов.

http://sp.cs.msu.ru/courses/prak2/lang_grams.pdf
 
 
Сообщения:2
И кстати нашёл ошибки в приоритетах формирования ОПН, точнее в порядке операций. К примеру выражение "4-5*(-2)" выдаст "-12", но правильный же ответ "14".
 
Модераторы:Нет
Сейчас эту тему просматривают:Нет