Польская нотация или к черту анализаторы

Приветствую, друзья!
Помнится, когда мы писали калькулятор арифметических выражений, нам понадобилось аж три статьи, чтобы это сделать: эта, эта и вот эта!

Все потому, что мы прошли через теорию и практику создания лексического и синтаксического анализатора, строили абстрактные синтаксические деревья - в общем, занимались таким непотребством, что в приличном обществе и вспоминать-то стыдно...

Но ведь цели можно достичь намного быстрее, хотя и не совсем обычным способом. В этот раз помощь пришла откуда не ждали - от польского математика Яна Лукасевича, который еще в 1920 году придумал так называемую польскую нотацию. В математике она не прижилась, а вот в программировании - дала буйные всходы. Познакомимся с его изобретением поближе. Все в Тардис!

На самом деле, Лукасевич открыл не одну, а целых две нотации: польскую и обратную польскую. В чем же разница?
Следим за руками! Обычно, математическое выражение записывается так:
 2 + 3
это обычный способ записи арифметических выражений, называемый также инфиксным (in - потому что знак сложения - между числами)

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

1. Инфиксная нотация (обычный способ, который изучают в школах): 2 + 3
2. Префиксная (польская) нотация: + 2 3
3. Постфиксная (обратная польская) нотация: 2 3 +

Применение

Это все конечно интересно и безумно увлекательно, возможно думает сейчас читатель, а зачем это все? Объясню.

Для программиста польская (и обратная польская) нотация удобна следующим:

1. Не нужны скобки. Да-да, те самые ненавистные скобки, ради которых мы городили абстрактное синтаксическое дерево - больше не нужны, поскольку приоритет операций теперь определяется тупо порядком следования чисел и операторов;
2. Поскольку скобки не нужны, программа, которая вычисляет выражения - упрощается до максимума. 

И вот как.

Алгоритм

Рассмотрим для простоты выражение, записанное в обратной польской нотации: 2 3 5 * +

Для нашего алгоритма понадобится такая структура данных, как стек, которую коротко описывают как "последним пришел - первым вышел". Кратко, алгоритм вычисления можно описать так:

1. Читаем выражение слева направо. Могут встретиться два типа значений: числа и операторы;
2. Если значение - число, то просто сохраняем его на вершине стека;
3. Если значение - оператор, то снимаем два числа с вершины стека, производим над ними соответствующую операцию, а результат сохраняем на вершине стека.

И это - все!!! Именно эта простота и привела к тому, что польская нотация навсегда осталась в сердцах программистов. Сначала рассмотрим пример этого алгоритма, на пальцах.

Пример

Разберем процесс вычисления выражения  2 3 5 * + по шагам.

1. Исходное состояние. Стек пуст. 
2. Читаем значение 2. Это - число. Переносим в стек;
3. Читаем значение 3. Это - число. Переносим в стек;
4. Читаем значение 5. Это - число. Переносим в стек;
5. Читаем значение *. Это оператор. Забираем числа 3 и 5 из стека. Перемножаем. Результат переносим в стек;
6. Читаем значение +. Это оператор. Забираем числа 2 и 15 из стека. Складываем. Результат отправляем в стек.
7. Выражение прочитано. В стеке - одно значение. Это и есть результат вычиления. Конец.

Код

Теперь, когда мы детально разобрали алгоритм, дело за малым - написать программу, которая будет вычислять выражения в обратной польской нотации. Реализация алгоритма проста, тривиальна и занимает совсем немного места, поэтому приведу ее сразу. Надеюсь за меня все скажут комментарии))

package ru.blogspot.toolkas.math.rpn;

import org.apache.commons.lang.StringUtils;
import org.apache.commons.lang.math.NumberUtils;

import java.util.Objects;
import java.util.Stack;

public class ReversePolishEvaluator {
    private static final String PLUS = "+";
    private static final String MINUS = "-";
    private static final String DIVIDE = "/";
    private static final String MULTIPLY = "*";

    public double eval(String expression) {
        //разбиваем строку пробелами
        String[] values = Objects.requireNonNull(expression).split(" ");

        Stack<Double> stack = new Stack<>();
        for (String value : values) {
            if (StringUtils.isBlank(value)) {
                //если встретился пробел - пропускаем и идем дальше
                continue;
            }

            if (NumberUtils.isNumber(value)) {
                //встретилось число - переносим в стек
                stack.push(Double.parseDouble(value));
            } else if (PLUS.equals(value)) {
                //Встретился знак сложения.
                //Читаем последнее число
                double val2 = stack.pop();
                //Читаем предпоследнее число
                double val1 = stack.pop();

                //Складываем числа
                double result = val1 + val2;
                //Результат сложения переносим в стек
                stack.push(result);
            } else if (MINUS.equals(value)) {
                //Встретился знак вычитания.
                //Читаем последнее число
                double val2 = stack.pop();
                //Читаем предпоследнее число
                double val1 = stack.pop();

                //Из предпоследнего числа вычитаем последнее
                double result = val1 - val2;
                //Результат вычитания переносим в стек
                stack.push(result);
            } else if (DIVIDE.equals(value)) {
                //Встретился знак деления.
                //Читаем последнее число
                double val2 = stack.pop();
                //Читаем предпоследнее число
                double val1 = stack.pop();

                //Делим предпоследнее число на последнее
                double result = val1 / val2;
                //Результат деления переносим в стек
                stack.push(result);
            } else if (MULTIPLY.equals(value)) {
                //Встретился знак умножения.
                //Читаем последнее число
                double val2 = stack.pop();
                //Читаем предпоследнее число
                double val1 = stack.pop();

                //Перемножаем числа
                double result = val1 * val2;
                //Результат перемножения переносим в стек
                stack.push(result);
            } else {
                throw new IllegalArgumentException("unsupported value: " + value);
            }
        }

        //Читаем результат вычисления из стека
        double result = stack.pop();

        //Если в стеке еще что-то осталось после вычислений - значит исходное выражение было некорректно. Ошибка
        if (!stack.isEmpty()) {
            throw new IllegalArgumentException("expression[" + expression + "] is incorrect");
        }

        return result;
    }
}

Итого

Ну вот и все, друзья. Задача решена довольно простым, но элегантным способом. 

Исходный код (конечно с тестами) программы, лежит тут. Спасибо Яну Лукасевичу за его прекрасное изобретение. Пора домой. Все - в Тардис!