Написати програму-інтерпретатор математичних виразів, що підтримує змінні та (в більш складному варіанті) оператори розгалуження. Можете взяти за основу вашу або чиюсь попередню лабораторну роботу із Shunting Yard.
В цій роботі замість того, щоб одразу обчислювати значення кожної операції, необхідно спочатку побудувати абстрактне синтаксичне дерево виразу. Далі обчислення виразу зводиться до обходу дерева в глибину і обчислення значення вузлів дерева або прийняття рішення про зміну порядку обходу дерева. Як приклад, можна навести умовний оператор: обчислюється лише одна з гілок вершини цього оператора, а інша пропускається.
Значення змінних під час обходу дерева найкраще зберігати в хеш-таблиці. Ніякі типи даних, крім чисел із плаваючою комою, впроваджувати не обов'язково.
AST використовують щоразу при компіляції програм написаних практично всіма мовами програмування. Наприклад, наступному фрагментові коду (приклад з вікіпедії)
while b ≠ 0
if a > b
a := a − b
else
b := b − a
return a
може відповідати таке дерево:
На вхід програмі подається текстовий файл з кодом, наприклад:
abc = 1;
q = 3;
2+abc*q;
Програма має вивести результат обчислення останнього виразу на екран:
result = 5.0
Синтаксис вашої мови можете вибрати будь-який. Програма має підтримувати змінні з іменем довжиною в будь-яку кількість символів, наприклад "a", "abc", "getthereveryfastindeed".
Складніший варіант (+1 бал): додати оператор if. Щоб не додавати булеві типи даних, можна вважати за true будь-яке відмінне від 0 число з плаваючою комою. Синтаксис оператора довільний (з дужками, без дужок, з endif, з блоками { }, або відступами, як у python), але це має бути не тернарний оператор. Наприклад,
a = if b then 1 else 2 або a = b ? 1 : 2 рівнозначні вирази. Перший варіант синтаксис python, другий - С. Обидва вирази є тернарними операторами, а не умовними.
Приклад правильного умовного оператора:
if D then
x1 = (b + sD) / (2 * a)
x2 = (b - sD) / (2 * a)
else
x = b / (2 * a)