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

Question

Я создаю CAS (систему компьютерной алгебры) на PHP, но я застрял прямо сейчас.Я использую этот сайт .

Теперь я написал токенизатор.Он преобразует уравнение, подобное этому:

1+2x-3*(4-5*(3x))

в следующее:

NUMBER PLUS_OPERATOR NUMBER VAR[X] MINUS_OPERATOR NUMBER MULTIPLY_OPERATOR GROUP

(где группа - это другой набор токенов).Как я могу упростить это уравнение?Да, я знаю, что вы можете сделать: добавить X-Vars, но они находятся в подгруппе.Какой лучший метод я могу использовать для обработки этих токенов?

Answer 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 + ...

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

Answer 2

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

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

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

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

Answer 3

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

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

var x = new Symbol("x");

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

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

-11 + 47 * x