Реализация калькулятора: какой алгоритм использовать?
Приветствую! Пишу приложение-калькулятор с бинарными/унарными функциями и скобками. Сейчас всё работает таким образом:
1. Все операнды и операторы кидаются в стек
2. При нажатии кнопки "=" запускается алгоритм сортировочной станции, который дальше считает результат в RPN
Однако задача в том, чтобы можно было видеть некий промежуточный результат, как в стандартных калькуляторах (например, для iPhone). То есть, унарное выражение считается отдельно (при нажатии на квадратный корень при выражении 2 + √(3+6) выводится результат "3", а дальше, если после этого нажать "+", то считается всё выражение с учетом приоритета). А бинарное выражение считается с учетом приоритета и выдает результат всех доступных вычислений (если приоритет следующей операции меньше, чем предыдущей).
Конечно, можно каждый раз при нажатии на бинарную операцию считать заново всё заново (расставляя ограничения по приоритетам), а при нажатии унарной -- считать отдельный регион, но что-то мне кажется, что это не особо оптимально.
Есть какие-нибудь еще варианты?
P.S. Наверное, требуется несколько уточнений:
а). Нынешняя реализация отлично считает готовое выражение;
б). Насколько я видел, калькуляторы считают бинарную операцию только тогда, когда встретилась следующая операция с приоритетом ниже ее (То есть, когда пользователь вводит 2 + 3 * , он не получает результат сложения, потому что нынешняя операция приоритетнее, а если после этого он захочет второй операнд возвести в степень, то отложится вычисление уже двух операций: 2 + 3 * 4 ^ 2);
в). У программы есть GUI, поэтому от нужен некий промежуточный результат;
г). Язык Swift (хотя это неважно, но вдруг);
Как я и предполагал, надо было создать стек отложенных бинарных операций. При добавлении новой бинарной операции в стек, нужно сравнить ее приоритет с приоритетом предыдущей операции, и если новая операция имеет меньший приоритет, то выполнить предыдущую. Со скобками почти то же самое, только там используется флаг.
Там есть окно с историей и непосредственно окно результата (или набора числа). Так что там будет такое отображение (И -- история, Р - результат):
Р: 2 И: 2
Р: 2 И: 2 +
Р: 2 И: 2 + (
Р: 3 И: 2 + (3
Р: 3 И: 2 + (3 +
Р: 6 И: 2 + (3 + 6
ну и так далее.
Было бы круто делать как-то всё пошагово, откладывать операции, пока есть более приоритетные операции, это надо стеки делать, но дальше этих мыслей у меня что-то не идет.
При валидных выражениях - вычисляйте теми же пунктами ("стек" и RPN).
Слева направо при выемке из стека - заменяйте исходное выражение: √(3+6) => 3
Валидация выражения на каждом шаге проверяется во время преобразования выражения в стек (в вопросе - п.1).
Badsignal, тогда используйте что-то иное вместо RPN, чем можно поделить целое выражение на отдельные токены, чтобы контролировать выражение и делать пересчёт только изменившегося токена.
Badsignal, думаю, что "слои" нужно "срезать" по приоритетам операций, помещая каждый слой в "дерево" из токенов минимальных операций (полученных из текущего выражения), чтобы при изменении узла - пересчитывать только зависимую "ветку" для отображения значения (а не всё целиком).
1-й слой (уровень 3): (3+6)
2-й слой (уровень 2): √[1-й слой]
3-й слой (уровень 1): 2 + [2-й слой]
4-й слой (root): [итог выражения]
И в обратную сторону - этот же алгоритм для построения "дерева": в скобках - уровни вложенности.
(но это я бы так стал делать....)
Простой
Средний