Какой алгоритм текстового калькулятора лучше?

Question

[sudo rm -rf /]

Есть два консольных калькулятора. Оба принимают текстовую строку как входное выражение и возвращают результат вычислений.

Первый перед вычислением рекурсивно (можно и итеративно) строит дерево, листья которого - положительные действительные числа, а остальные узлы - операции. Для построения дерева приоритет операций инвертируется - сначала выбираются операции с наименьшим приоритетом, не разбивая скобок. После выбора операции выражение разбивается на две части по знаку операции - операнды. Выражения-операнды рассматриваются как отдельные выражения: их разбиение продолжается независимо друг от друга. При получении результата вычисления двух операндов-выражений над полученными значениями выполняется операция. Результат операции возвращается.
Алгоритм одного вызова функции разбора Calc(String expr):

1. Поиск операций в expr с учётом приоритета и сохранения скобочной структуры; или преобразование строки в число и возврат значения.
   
2. Разбиение expr на два подвыражения по найденному знаку операции - oper1, oper2
   
3. Рекурсивное разбиение: res1 = Calc(oper1); res2 = Calc(oper2);
   
4. Вычисление результата найденной операции над res1 и res2 - o_res.
   
5. Возвращение o_res.
   

При этом второй калькулятор работает с выражением "как в школе", модифицируя строку: выбирает элементарную операцию (операнды - числа) с наибольшим приоритетом, вычисляет её значение, заменяет выражение значением, получая упрощённое выражение и повторяет процедуру до получения валидного числа, которое можно привести и вернуть.

Какой из этих подходов лучше? Какие "подводные камни"?
Есть ли более подходящие альтернативы?

Comments

[Денис Загаевский]

сам-то как думаешь?

Answer 1

[dsadso]

Посмотрите на обратную польскую запись. Самое простое что может быть.
https://habr.com/ru/post/100869/

Answer 2

[Сергей Тихонов]

Добро пожаловать в мир конструирования компиляторов :)
Если кратко и просто, то основные стадии работы компилятора такие:

1. Лексический анализ (разделение строки на лексемы - числа и операции)
   
2. Синтаксический анализ (скобки, приоритет операций - в общем, перевод потока лексем во внутреннее представление
   
3. Дальше уже не компилятор а интерпретатор начинается: вычисление значений выражений.
   

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

Answer 3

[tsarevfs]

Польская запись -- простой и незатейлевый алгоритм. Работает с выражениями содержащими бинарные операции и скобки. Вероятно ваш выбор.
Низходящий разбор это то что вы пытались описать под первым пунктом. Он более универсален. Позволяет разбирать более сложные грамматики c унарными операциями и контекстной завичимостью (один знак может иметь разные значения в зависимости от контекста). В этом методе больше подводных камней. Нужно изучить много теории чтобы понять как обойти некоторые сложности, например левую рекурсию. При некоторой настойчивости можно разобраться.
Восходящий разбор. SLR, LALR парсеры. Активно применяются на практике. Они сложные, их нет практического смысла писать самостоятельно. Если вы будете использовать генератор парсеров Bison, то это оно.

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

Comments

[sudo rm -rf /]

"Разбивается"? Каким образом?

[tsarevfs]

sudo rm -rf /,
Пожалуй я бы не прав. Такой алгоритм возможен, но потребует O(n^2) операций. Для того чтобы выбрать операцию с максимальным приоритетом в выражении 1+1+1+..+1 нужно просмотреть всю строчку из n слагаемых. Дальше вы проведете замену 2+1+..+1 и повторите. В итоге получаем n + (n-1) + (n-2) + ... + 1 = n * (n + 1) / 2 = O(n^2) операций.
Польскую запись можно построить и вычислить быстрее, за O(n).