Построение системы компьютерной алгебры

Ответ 1

На самом деле полезным следующим шагом было бы построить дерево разбора:

Вы сделали бы один из них, написав инфиксный парсер. Вы могли бы сделать это, написав простой рекурсивный парсер спуска или при помощи больших пушек и с использованием генератора парсера. В любом случае это помогает построить формальную грамматику:

expression: additive

additive: multiplicative ([+-] multiplicative)*

multiplicative: primary ('*' primary)*

primary: variable
       | number
       | '(' expression ')'

Обратите внимание, что эта грамматика не обрабатывает синтаксис 2x, но ее следует легко добавить.

Обратите внимание на умное использование рекурсии в правилах грамматики. primary фиксирует только переменные, числа и выраженные в скобках выражения и останавливается при запуске оператора. multiplicative анализирует один или несколько выражений primary, обозначенных знаками *, но останавливается, когда наступает знак + или -. additive анализирует один или несколько выражений multiplicative, разделенных символами + и -, но останавливается, когда он запускается в ). Следовательно, схема рекурсии определяет приоритет оператора.

Не слишком сложно реализовать прогностический парсер вручную, как я сделал ниже (см. полный пример на 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 + ...

Я оставлю эту часть вам. Наличие дерева синтаксического анализа должно сделать вещи намного более простыми.

Ответ 2

PHP хорош для строк, чисел и массивов. Но это плохой язык для реализации манипуляций с символическими формулами, поскольку у него нет собственного механизма обработки "символических выражений", для которого вы действительно хотите деревья. Да, вы можете реализовать все эти механизмы. Труднее делать алгебраические манипуляции. Его довольно много работы, если вы хотите сделать что-то полу-сложное. В идеале вы хотите, чтобы оборудование помогало вам писать преобразования прямо и просто.

Например, как вы будете реализовывать произвольные правила алгебры? Ассоциативность и коммутативность? Термин "сопоставление на расстоянии"?, например,

  (3*a+b)-2(a-b)+a ==> 3a-b

Вы можете посмотреть, как можно выполнить простой CAS, используя наш Система преобразования программ DMS. DMS имеет жесткие математические конструкции, такие как коммутация и ассоциативность, и вы можете явно писать правила алгебр, чтобы работать с символическими формулами.

Ответ 3

Книга Компьютерная алгебра и символические вычисления: математические методы Джоэля С. Коэна описывает алгоритм автоматического упрощения алгебраических выражений.

Этот алгоритм используется в библиотеке компьютерной алгебры Symbolism для С#. Следуя приведенному ниже примеру С#:

var x = new Symbol("x");

(1 + 2 * x - 3 * (4 - 5 * (3 * x)))
    .AlgebraicExpand()
    .Disp();

отображает на консоли следующее:

-11 + 47 * x