Калькулятор с решением. Как реализовать?

Question

[Василий Васильев]

Задача: реализовать калькулятор с выводом пошагового решения простых уравнений.
Входные данные: строка неопределенной длинны. Действия: +; -; *; /;
Выходные данные: пошаговое решение уравнения.
Пример:
Входные данные: 2 + 2 * 2 / 2 - 2 * 4 / 2
Выходные данные:
2 + 2 * 2 / 2 - 2 * 4 / 2 =
2 + 4 / 2 - 8 / 2 =
2 + 2 - 4 =
4 - 4 = 0

Есть какие-нибудь идеи?

Comments

[gleendo]

Роберт Лафоре | Структуры данных и алгоритмы в Java
В данной книге есть подробное описание реализации мат.интерпритатора, вроде как даже с выводом промежуточных результатов. Возможно чем то поможет.

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

Это не уравнение

Answer 1

[Максим Мосейчук]

Оптимизация свёрткой. Список промежуточных шагов и есть решение.
https://ru.wikipedia.org/wiki/%D0%A1%D0%B2%D1%91%D...

Comments

[Василий Васильев]

но как именно выудить эти промежуточные шаги?

[Максим Мосейчук]

Basil_Dev: Ну после парсинга у вас должно получится синтаксическое дерево. Узлы, находящиеся на одном расстоянии от корня, соответствуют операциям с одинаковым приоритетом.

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

И так до тек пор, пока корень дерева не станет константным выражением.

Answer 2

[anwender95]

Мой говнокод на c++, который реализует пошаговое решение уравнений(с учетом приоритетов операторов) и поддерживаются переменные и константы. Слегка не дописан, но есть интерпретатор коммандной строки.