構建計算機代數系統

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