构建计算机代数系统

Question

我正在用PHP创建一个CAS(计算机代数系统),但我现在卡住了.我正在使用这个网站.

现在我写了一个tokenizer.它将转换如下的等式:

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

对此:

NUMBER PLUS_OPERATOR NUMBER VAR[X] MINUS_OPERATOR NUMBER MULTIPLY_OPERATOR GROUP

(其中group是另一组令牌).我该如何简化这个等式？是的,我知道你能做什么:添加X-vars,但它们在子组中.我可以用来处理这些令牌的最佳方法是什么？

Answer 1

一个非常有用的下一步是构造一个解析树:

你可以通过编写一个中缀解析器来创建其中一个.您可以通过编写一个简单的递归下降解析器,或通过引入大枪并使用解析器生成器来完成此操作.在任何一种情况下,它都有助于构建一个正式的语法:

expression: additive

additive: multiplicative ([+-] multiplicative)*

multiplicative: primary ('*' primary)*

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

请注意,此语法不处理2x语法,但应该很容易添加.

注意在语法规则中巧妙地使用递归. primary仅捕获变量,数字和带括号的表达式,并在运行到运算符时停止. multiplicative解析一个或多个primary由分隔符的表达式*的迹象,但是当它运行到停止+或-标志. additive解析multiplicative由+and 分隔的一个或多个表达式-,但在它遇到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 + ...

我会把那部分留给你.使用解析树应该使事情变得更加简单.