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

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

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

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

к этому:

NUMBER PLUS_OPERATOR NUMBER VAR[X] MINUS_OPERATOR NUMBER MULTIPLY_OPERATOR GROUP

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

Источник

3 ответа

Решение

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

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

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

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

Источник

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

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

  (3*a+b)-2(a-b)+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
Источник
Другие вопросы по тегам