Построение системы компьютерной алгебры
Я создаю CAS (компьютерная алгебра система) в PHP, но я застрял прямо сейчас. Я использую этот сайт .
Теперь я написал токенизатор. Он преобразует уравнение следующим образом:
1+2x-3*(4-5*(3x)) к этому:
NUMBER PLUS_OPERATOR NUMBER VAR[X] MINUS_OPERATOR NUMBER MULTIPLY_OPERATOR GROUP
(где группа – это еще один набор токенов). Как я могу упростить это уравнение? Да, я знаю, что вы можете сделать: добавление X-vars, но они находятся в подгруппе. Каков наилучший метод, который я могу использовать для обработки этих токенов?
На самом деле полезным следующим шагом было бы построить дерево разбора:
Вы сделали бы один из них, написав инфиксный парсер. Вы можете сделать это, написав простой рекурсивный парсер спуска или введя большие пушки и используя генератор парсера . В любом случае это помогает построить формальную грамматику:
expression: additive additive: multiplicative ([+-] multiplicative)* multiplicative: primary ('*' primary)* primary: variable | number | '(' expression ')'
Обратите внимание, что эта грамматика не обрабатывает синтаксис 2x , но ее следует легко добавить.
Обратите внимание на умное использование рекурсии в правилах грамматики. primary только фиксирует переменные, числа и выраженные в скобках выражения и останавливается при запуске в оператор. multiplicative анализ одного или нескольких primary выражений, обозначенных символами * , но останавливается, когда он пробегает знак + или. additive анализирует одно или несколько multiplicative выражений, разделенных символами + и - , но останавливается при запуске в a ) . Следовательно, схема рекурсии определяет приоритет оператора.
Слишком сложно реализовать прогностический парсер вручную, как я сделал ниже ( см. Полный пример на ideone.com ):
function parse() { global $tokens; reset($tokens); $ret = parseExpression(); if (current($tokens) !== FALSE) die("Stray token at end of expression\n"); return $ret; } function popToken() { global $tokens; $ret = current($tokens); if ($ret !== FALSE) next($tokens); return $ret; } function parseExpression() { return parseAdditive(); } function parseAdditive() { global $tokens; $expr = parseMultiplicative(); for (;;) { $next = current($tokens); if ($next !== FALSE && $next->type == "operator" && ($next->op == "+" || $next->op == "-")) { next($tokens); $left = $expr; $right = parseMultiplicative(); $expr = mkOperatorExpr($next->op, $left, $right); } else { return $expr; } } } function parseMultiplicative() { global $tokens; $expr = parsePrimary(); for (;;) { $next = current($tokens); if ($next !== FALSE && $next->type == "operator" && $next->op == "*") { next($tokens); $left = $expr; $right = parsePrimary(); $expr = mkOperatorExpr($next->op, $left, $right); } else { return $expr; } } } function parsePrimary() { $tok = popToken(); if ($tok === FALSE) die("Unexpected end of token list\n"); if ($tok->type == "variable") return mkVariableExpr($tok->name); if ($tok->type == "number") return mkNumberExpr($tok->value); if ($tok->type == "operator" && $tok->op == "(") { $ret = parseExpression(); $tok = popToken(); if ($tok->type == "operator" && $tok->op == ")") return $ret; else die("Missing end parenthesis\n"); } die("Unexpected $tok->type token\n"); }
Хорошо, теперь у вас есть это прекрасное дерево синтаксиса и даже красивая картинка, чтобы пойти с ним. Что теперь? Ваша цель (на данный момент) может состоять в том, чтобы просто объединить термины, чтобы получить результат формы:
n1*a + n2*b + n3*c + n4*d + ...
Я оставлю эту часть тебе. Наличие дерева синтаксиса должно сделать вещи намного более простыми.
PHP хорош для строк, чисел и массивов. Но это плохой язык для реализации манипуляций с символическими формулами, поскольку у него нет собственного механизма обработки «символических выражений», для которого вы действительно хотите деревья. Да, вы можете реализовать все эти механизмы. Труднее делать алгебраические манипуляции . Его довольно много работы, если вы хотите сделать что-то полу-сложное. В идеале вы хотите, чтобы машины помогали вам писать преобразования прямо и просто.
Например, как вы будете применять произвольные правила алгебры? Ассоциативность и коммутативность? Термин «сопоставление на расстоянии» ?, например
(3*a+b)-2(ab)+a ==> 3a-b
Вы можете посмотреть, как простой CAS может быть реализован с использованием нашей системы преобразования программ DMS . DMS имеет жесткие математические конструкции, такие как коммутация и ассоциативность, встроенные, и вы можете писать правила алгебр явно для работы с символическими формулами.
Книга « Компьютерная алгебра и символические вычисления: математические методы» Джоэля С. Коэна описывает алгоритм автоматического упрощения алгебраических выражений.
Этот алгоритм используется в библиотеке компьютерной алгебры Symbolism для C #. Следуя приведенному ниже примеру C #:
var x = new Symbol("x"); (1 + 2 * x - 3 * (4 - 5 * (3 * x))) .AlgebraicExpand() .Disp();
отображает на консоли следующее:
-11 + 47 * x