构建计算机代数系统

Question

我在PHP中创建了一个CAS（计算机代数系统），但我现在被卡住了。我正在使用this website。

现在我写了一个标记器。它将一个方程转换是这样的：

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

这样：

NUMBER PLUS_OPERATOR NUMBER VAR[X] MINUS_OPERATOR NUMBER MULTIPLY_OPERATOR GROUP 

（其中基团是另一组的令牌）。我怎样才能简化这个方程？是的，我知道你可以做什么：添加X-vars，但它们在子组中。我可以用来处理这些令牌的最佳方法是什么？

Answer 1

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

你会成为其中一个写的缀解析器。你可以通过编写一个简单的递归下降解析器，或者通过引入大枪和using a parser generator来做到这一点。在这两种情况下，它有助于建立一个正式的语法：

expression: additive 

additive: multiplicative ([+-] multiplicative)* 

multiplicative: primary ('*' primary)* 

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

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

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

这是不是太可怕难以实现predictive parser手，因为我已经做了以下（see full example at 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 

你可以看一下如何使用a simple CAS can be implemented我们DMS program transformation system。 DMS具有很强的数学结构，如内置的交换性和关联性，您可以明确地编写代数规则以操作符号公式。

Answer 3

该书 Computer Algebra and Symbolic Computation: Mathematical Methods by Joel S. Cohen 描述了一种自动简化代数表达式的算法。

该算法用于C＃的Symbolism计算机代数库。你的榜样去，下面的C＃程序：

var x = new Symbol("x"); 

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

显示在控制台以下：

-11 + 47 * x