컴퓨터 대수학 시스템 구축

Question

저는 PHP로 CAS (Computer Algebra System)를 만들었지 만 지금은 막혀 있습니다. 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을 가져 와서이 작업을 수행 할 수 있습니다. 두 경우 모두, 그것은 형식적인 문법을 구성하는 데 도움이 문법은 2x 구문을 처리하지 않는

expression: additive 

additive: multiplicative ([+-] multiplicative)* 

multiplicative: primary ('*' primary)* 

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

참고하지만, 쉽게 추가 할 수 있어야합니다.

문법 규칙에서 재귀를 영리하게 사용합니다. primary은 변수, 숫자 및 괄호로 묶은 표현식 만 캡처하고 연산자로 실행되면 중지합니다. multiplicative은 * 기호로 구분 된 하나 이상의 primary 표현식을 구문 분석하지만 + 또는 - 기호로 실행되면 중지합니다. additive은 + 및 -으로 구분 된 하나 이상의 multiplicative 수식을 구문 분석하지만 )으로 실행되면 중지합니다. 따라서 재귀 체계는 연산자 우선 순위를 결정합니다. 심지어 꽤 당신이 아름다운 파스 트리가 그래서 지금,

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"); 
} 

이 좋아, 그리고 : 나는 (see full example at ideone.com) 아래에했던 것처럼

이는 predictive parser 손으로 구현하기 너무 몹시 어려운 일이 아니다 그것으로가는 그림. 이제 뭐?귀하의 목표는 (지금은) 간단히 용어를 결합하여 양식의 결과를 얻을 수 있습니다.

n1*a + n2*b + n3*c + n4*d + ... 

나는 그 부분을 남겨 둘 것입니다. 구문 분석 트리를 사용하면 훨씬 간단하게 작업을 수행 할 수 있습니다.

Answer 2

PHP는 문자열, 숫자 및 배열을 잘 처리합니다. 그러나 상징적 인 수식 조작을 구현하기에는 가난한 언어입니다. 왜냐하면 실제로 나무를 원한다는 "상징적 표현"을 처리 할 고유의 기계가 없기 때문입니다. 예, 모든 기계류를 구현할 수 있습니다. 더 단단한 것은 에 대수적 조작을합니다.. 아주 정교한 무언가를 만들고 싶다면 꽤 많은 일을해야합니다. 변환을 직접적이고 쉽게 작성하는 데 도움이되는 기계가 가장 이상적입니다.

예를 들어 임의의 대수 규칙을 어떻게 구현합니까? 연합성과 commutativity? 용어 "거리를두고 일치하는"?

(3*a+b)-2(a-b)+a ==> 3a-b 

당신은 우리의 DMS program transformation system를 사용하는 방법 a simple CAS can be implemented 볼 수 있습니다. DMS는 commutativity 및 associativity와 같은 어려운 수학적 구조를 가지고 있으며 대수학 규칙을 명시 적으로 작성하여 기호식에 적용 할 수 있습니다.

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