Калькулятор в PHP: обробка математичного виразу як рядка

16. 02. 2020

Obsah článku

Уявіть, що перед вами стоїть завдання обробити простий математичний приклад, який користувач вводить у вигляді текстового рядка, наприклад, в пошуковий рядок. Як правило, користувач хоче виконати просту числову операцію з числами. Ця стаття описує процес мислення та конкретні інструкції, як це зробити.

Наївна імплементація

Довгий час мені було цікаво, чи можна простий математичний вираз обробити якимось трюком, щоб зробити код якомога коротшим... і через багато років я фактично маю розв'язок.

Розглядайте наведене рішення лише як приклад, оскільки воно вкрай небезпечне і недобросовісний користувач може легко підкреслити рядок, що, наприклад, призведе до видалення всього додатку або викрадення бази даних!

// Запит користувача
$query = '5 + 3 * 2';

// Обробка виразу як звичайного PHP-коду
eval('$result = @(' . $query . ');');

// Лістинг змінної з розв'язком виразу
echo $result; // виводить 11

Хитрість полягає в тому, що функція eval() виконує рядок так, ніби він знаходиться в контексті коду PHP. Це божевілля, але воно працює. Обгортка пригнічує повідомлення про помилки.

Робота з більш складними вхідними даними

Крім того, що обробка виразів через eval() вкрай небезпечна, вона ще й не дає достатньо красномовного синтаксису, який би влаштовував усіх. Якщо користувач допустить хоча б одне синтаксичне порушення, то весь вираз не зможе бути оброблений.

Тому рішення полягає в тому, щоб спочатку зрозуміти і виправити запит користувача за формальним аспектом (що називається нормалізацією до канонічної форми), а потім передати і обробити його далі.

Я програмував QueryNormalizer саме для цієї задачі в минулому.

Сама обробка є дуже складним завданням, адже потрібно правильно розуміти різні контексти. Наприклад, що круглі дужки позначають вкладені блоки і мають обчислюватися рекурсивно. Наприклад, вираз 5+2^(1+3/2) не можна розв'язати прямолінійно, тому що спочатку треба розв'язати дріб, додати його до числа в дужках, потім розв'язати для цілого степеня, і, нарешті, додати на рівні піднесення до степеня.

Щоб навіть задовольнити цю вимогу, вираз вже не може розглядатися як звичайний рядок, і ми повинні вийти на рівень абстракції. По суті, математика - це своєрідна мова, яка описує взаємозв'язки між операціями та числами, адже нам доводиться мати справу з пріоритетами операторів, різними значеннями, контекстами, рекурсією і навіть типами даних. Ось тут і відбувається процес токенізації запиту.

Я працюю над проблемою математичної токенізації з 2015 року і за цей час написав кілька різних парсерів.

Найкращий з них, на якому наразі працює новий "Математик", є [доступним з відкритим кодом на GitHub] (https://github.com/mathematicator-core/tokenizer).

Суть токенізації полягає в розборі рядка, розбитті його на групи менших рядків відомих типів, а потім перетворенні їх в об'єкти (типи даних). Потім перетворений масив об'єктів перетворюється за допомогою розумної логіки в бінарне дерево, яке може описувати залежності та рекурсію. Це дуже складний процес, оскільки існують сотні можливих сценаріїв, і користувачі можуть бути дуже креативними у своїх запитах.

Основною перевагою масиву токенів є те, що його можна дуже легко передати на наступний рівень, який, наприклад, виконує власне обчислення, або перемальовує дерево в LaTeX.

Використання може виглядати елегантно ось так:

$tokenizer = new Tokenizer(/* деякі залежності */ ** деякі залежності */);

// Перетворити математичну формулу в масив токенів:
$tokens = $tokenizer->tokenize('(5+3)*(2/(7+3))');

// Тепер ви можете конвертувати токени в більш корисний формат:
$objectTokens = $tokenizer->tokensToObject($tokens);

dump($objectTokens); // Повернути типізовані токени з метаданими

// Відрендерити в LaTeX
echo $tokenizer->tokensToLatex($objectTokens);

// Рендер в налагоджувальне дерево (дуже швидко):
echo $tokenizer->renderTokensTree($objectTokens);

Перегляд процедур

Значна кількість користувачів оцінить, коли при розрахунку програма відображає процедуру, щоб показати, як вона це зробила. Це насправді корисно і для програміста, адже принаймні він може легко з'ясувати, де є помилка в обчисленні, і відповідно виправити алгоритм. Коли ви поєднуєте все це з машинним навчанням на основі автоматизованих тестів, ви отримуєте щось дивовижне.

Подивіться, як QueryNormalizer зміг зрозуміти ваш запит, передав дані токенізатору, той відрендерив запит в LaTeX відповідно до нього, а потім передав дерево об'єктів калькулятору, який повернув загальний результат.

Příklad: 5+2^(1+3/2).

Представлення процедури реалізовано за допомогою обчислювача, який проходить по вхідному дереву та обчислює по одному правилу за раз відповідно до маркерів та правил, що містяться в ньому. Коли будь-яке правило оцінюється, воно поміщає інформацію про крок в масив. Іноді крок може виявитися невірним і нам доведеться повернутися назад і піти іншим шляхом в розрахунку, але за цим стоїть досить багато магії, яка поки що залишиться прихованою і ви зможете вивчити її в процесі реалізації.

Висновок

Наведена вище процедура описує, як елегантно поводитися з математичними виразами, де є числа, операції та відношення з ними. Цей підхід не може, наприклад, модифікувати вирази або розв'язувати рівняння, але ми розглянемо це наступного разу.

*Якщо у вас є інші ідеї щодо того, як ефективно обробляти математичні дані, я буду радий почути їх від вас.

Jan Barášek Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu: