Символьная арифметика

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

Например, выражение "2*(3+4)" будет представлено вот таким деревом:

В программе узлы дерева представляются объектами типов, унаследованных от интерфейса Expression, который объявлен в файле Common.h. У интерфейса есть два метода:

• Evaluate() возвращает численное значение выражения. Для нашего примера это будет 14
• ToString() форматирует выражение как строку. Для простоты реализации, чтобы не учитывать приоритеты операций, каждый узел берётся в скобки. То есть для нашего примера этот метод вернёт "(2)*((3)+(4))"

Так как Expression — это абстрактный класс, работать с ним можно только через указатель или ссылку. Чтобы не заниматься ручным управлением памятью, будем использовать умный указатель unique_ptr. Чтобы не загромождать код выражениями unique_ptr<Expression>, в файле Common.h для этого выражения предоставлен синоним ExpressionPtr.

Реализуйте функции, которые позволяют создавать такое дерево выражения. Они объявлены в файле Common.h:

• Value() возвращает дерево из одного узла, представляющего целое число.
• Sum() возвращает новое дерево, которое представляет сумму двух переданных выражений.
• Product() возвращает новое дерево, которое представляет произведение двух переданных выражений.

Таким образом, следующий код создаст дерево для выражения "2*(3+4)":

Product(Value(2), Sum(Value(3), Value(4)));

Указания

• Нужно определить класс-наследник интерфейса Expression. Этот класс-наследник нужно создавать в функциях Value(), Sum() и Product() с помощью функции make_unique().
• Класс-наследник должен содержать в себе указатели на поддеревья, как члены типа ExpressionPtr. Таким образом, узел-родитель будет владеть узлами-детьми. Корневым узлом будет владеть вызывающий код. В методах Sum() и Product() переданные поддеревья нужно перемещать внутрь созданного экземпляра класса.
• Вместо одного класса-наследника лучше создать небольшую иерархию классов. Например, если узел дерева представляет число (то есть является листом), хранить в нём указатели на поддеревья не имеет смысла. Аналогично, если узел представляет двоичную операцию (сложение или умножение), то хранить в нём целое число тоже бессмысленно. Таким образом, класс, который представляет число, и класс, который представляет двоичную операцию, стоит сделать независимыми наследниками Expression. Также имеет смысл сделать отдельный класс под каждую из двоичных операций, чтобы убрать дублирование кода, и избежать логики, построенной на проверках ("if-based logic"). Все они будут наследоваться от класса, представляющего двоичную операцию.

Примечания и уточнения

• Классы-наследники и функции Value(), Sum() и Product() можно реализовать либо только в файле Common.cpp, либо разнести реализацию по нескольким *.h и *.cpp файлам, но эти файлы должны лежать в корне - там же, где и Common.h.
• Формат метода ToString() фиксирован. Возвращаемая строка не должна содержать ничего постороннего - только целые числа, скобки () и знаки + и *. В строке не должно быть пробелов и переносов строк, каждый узел должен быть взят в скобки, нельзя переставлять местами слагаемые и множители и т.д., иначе тесты не пройдут.

Как тестировать локально

Собрать программу с помощью cmake и запустить ctest:

mkdir build; cd build
cmake ..; cmake --build .
ctest -V