PHP에서 표현식 트리를 사용하는 방법은 무엇입니까?

Question

저는 현재 방정식을 푸는 PHP 프로그램을 만들고 있습니다. 배열의 각 줄마다 하나의 항이 포함되도록 입력 방정식을 배열로 나눴습니다. (So. [0] = "+ 5x", [1] = "=", [2] = "-5", [3] = "+10"이 스크립트는 기본적인 방정식입니다. 예를 들어 2x + (5-3x) = 3 (x + 1) [0] = "+ 2 * x", [1] = array ([0] = "+5" ....

그러나이 방정식 해결사에서 사용할 수있는 표현식 트리를 발견했습니다. 전체 인터넷을 검색하여 학습했지만이를 설명하는 웹 사이트를 찾을 수 없습니다. PHP (PHP OOP를 알고 있습니다.) 예를 들어 C를 예로 들어 설명하는 페이지가 많이 있지만 예제 코드를 이해할 수 없기 때문에 PHP 만 알면 도움이되지 않습니다.

누구든지 가능합니다. 여기 PHP의 표현식 트리와 실용적인 예제 코드에 대한 모든 것을 설명합니다.

Answer 1

Here is the algorithm이 기재되어있다. 이것을 PHP로 구현할 수 있습니다. 나는 예는 될 사람이 이미 PHP에서 이것을 구현 생각 (그리고 그것을 오픈 소스로 배포)

을하지 않습니다

2*x+3*5-(6+9) = 0 

장소 :

• * = 우선 순위 2
• + = 우선 순위 1
• ( = 부호의 우선 순위가 10만큼 증가합니다.
• + (초 +) = 우선 11
• ) = 이러한 경우에 다른 식 (0)

가장 높은 우선 순위가 있음을 보이고있다 = 10

= 의해 기호 우선 감소 가장 중요하다 - ... 하나는 당신이 당신이 식 트리를 만들 수 있습니다 이러한 규칙을 사용하여 첫 번째

을 할 필요가

그래서 ..하는 방식으로 당신이 표현을 생성해야하고 해석하는 것입니다 :

2 x * 3 5 * + 6 9 + - 

는 설명 :

• 2 * x | (1)
• 3 * 5 | (2)
• (1) + (2) | (3)
• 6 + 9 | (4)
• (3) - (4) = final
,

나는 컴퓨터 과학 과정에 이런 짓을 나무를 작성하는 방법을 정확히 기억하지 않습니다하지만이 같은했다 :

         - 
           /  \ 
           E   (E) 
           |   + 
           +  /\ 
          / \  6 9 
          E  E   
          |  |  
          *  * 
         /\ /\  
          T E T E 
          | | | | 
          2 T 3 T 
           |  | 
           x  5 

지금이에 대한 자신의 통역을 만들어야합니다.인터프리터 패턴을 사용할 수 있습니다. PHP Interpreter

Answer 2

표현 트리에 대해 Composite design pattern에 대해 조금 읽으십시오. Wikipedia에 관한 기사에는 UML 다이어그램과 예제 Java 코드가 포함되어 있습니다.이 코드는 PHP로 번역하기가 어렵지 않습니다.

Shunting-yard 알고리즘을 살펴보고 문자열을 구문 분석 트리로 구문 분석 할 수 있습니다. 식 트리

A (매우 단순한) PHP의 예는 다음과 같을 수있다 :

이때

interface INode { 
    public function getValue(); 
} 

class ValueNode implements INode { 
    private $val; 

    function __construct($val) { 
     $this->val = $val; 
    } 

    public function getValue() { 
     return $this->val; 
    } 
} 

class AdditionNode implements INode { 
    private $op1, $op2; 

    function __construct($op1, $op2) { 
     if(!($op1 instanceof INode) or !($op2 instanceof INode)) { 
      throw new Exception("The operands must implement the INode interface."); 
     } 

     $this->op1 = $op1; 
     $this->op2 = $op2; 
    } 

    public function getValue() { 
     return $this->op1->getValue() + $this->op2->getValue(); 
    } 
} 


$a = new ValueNode(1); 
$b = new ValueNode(5); 
$c = new ValueNode(10); 
$add1 = new AdditionNode($a, $b); 
$add2 = new AdditionNode($add1, $c); 

echo $add2->getValue(); // 16 

에서, INode 인터페이스에서 루트로하는 서브 트리의 값을 반환한다 한 방법을 갖는다 노드.

ValueNode 클래스는 숫자가 표현식 트리의 일부가되도록 허용하는 간단한 래퍼입니다 (사실 PHP에서는 ValueNode의 숫자로만 제한되지 않습니다). ValueNode 개체는 표현식 트리에서 리프 노드로만 제공 될 수 있습니다.

INode 개체를 어린이로 받아들이고 표현 트리를 만드는 데 도움이되는 AdditionNode 클래스로 복합 패턴을 사용하기 시작합니다.

이 예제를 확장하여 INode 인터페이스를 모두 구현하는 다른 연산, 변수, 상수 등을 추가 할 수 있습니다.

Answer 3

몇 년 전 this utility에 대괄호 파서를 작성했습니다. 거의 모든 깊이의 괄호 된 SQL WHERE 표현식을 사용하고이를 PHP Propel 코드로 변환합니다. 전체 타르볼은 here이고 구문 분석은 here에서 시작됩니다. 코드는 좀 더 세련 될 수 있으며 공식적인 표현 분석 기법에 익숙하지 않다는 것을 명심하십시오.하지만 패션 후에는 작동합니다. :).

Answer 4

수학 표현식을 구문 분석하고 문제를 해결하기 위해 PHP에서 표현 트리를 만들었습니다. 당신은 여기에서 원인을 찾을 수 있습니다 http://codehackit.blogspot.com/2011/08/expression-parser-in-php.html

나는 거의 그 블로그 게시물의 모든 세부 사항을 설명하지만 당신은 어떤 모호성 그냥 여기 물어 찾을 경우)

건배,이 도움이 적어도 잘