构建计算机代数系统

Question

我正在用 PHP 创建 CAS（计算机代数系统），但现在陷入困境。我正在使用此网站。

现在我写了一个分词器。它将这样的方程转换

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

为：（

NUMBER PLUS_OPERATOR NUMBER VAR[X] MINUS_OPERATOR NUMBER MULTIPLY_OPERATOR GROUP

其中 group 是另一组标记）。我怎样才能简化这个方程？是的，我知道你可以做什么：添加 X 变量，但它们位于子组中。处理这些令牌的最佳方法是什么？

Answer 1

真正有用的下一步是构建一个解析树：

您可以通过编写其中一个中缀解析器。您可以通过编写一个简单的递归下降解析器来做到这一点，或者通过引入大枪和 使用解析器生成器。无论哪种情况，它都有助于构建正式语法：

expression: additive

additive: multiplicative ([+-] multiplicative)*

multiplicative: primary ('*' primary)*

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

请注意，此语法不处理 2x 语法，但它应该很容易添加。

请注意语法规则中递归的巧妙使用。 primary 仅捕获变量、数字和括号表达式，并在遇到运算符时停止。 multiplicative 解析由 * 符号分隔的一个或多个 primary 表达式，但当遇到 + 或 <代码>-符号。 additive 解析由 + 和 - 分隔的一个或多个 乘法 表达式，但在遇到 时停止>)。因此，递归方案决定了运算符的优先级。

手动实现 预测解析器 并不太困难，因为我已完成以下操作（在 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

这本书
计算机代数和符号计算：Joel S. Cohen 的数学方法
描述了一种自动简化代数表达式的算法。

此算法用于 C# 的 Symbolism 计算机代数库。按照您的示例，以下 C# 程序：

var x = new Symbol("x");

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

在控制台上显示以下内容：

-11 + 47 * x