표현식을 이진 트리로 변환하는 알고리즘

Question

수식을 가지고있는 과제가 있습니다. x+(y*z)을 입력하고 이진 트리로 변환해야합니다. 나는 온라인으로 보았고 infix과 postfix과 같은 키워드를 보았고 정규식을 더 쉽게 이진 트리로 쉽게 변환 할 수있는 형식으로 변환하는 데 도움이됩니다.

내 유일한 문제는이 infix 또는 postfix 메서드를 배운 적이 없으므로 다른 방법으로 변환 할 수 있습니까, 아니면 유일한 방법입니까? 나는 위로 찾는 것으로 시도했다. 그러나 이것들은 내가 얻었던 유일한 결과이었다.

온라인 리소스를 사용하지 않고도 해결하기가 어려운 문제입니다.

Answer 1

중첩과 후위는 표기법이나 같은 수식을 표현하는 방법 그 자체가 아닙니다. x+(y*z)은 이미 중위 표기법으로되어 있습니다 (연산자가 인 경우에 해당하므로). 다른 두 표기법은 연산자가 피연산자 (예 : x+(y*z)은 + x * y z) 앞에 붙는 후행 (또는 역방향 폴란드어 표기법)이며 연산자가 피연산자 뒤에 오도록하는 접두사 (또는 폴란드어 표기)입니다 (따라서 은 y x * x + 임). 당신은 스택에 y 및 x를 넣어 y x * x +가 쉽게 스택을 통해 구현 될 수 있기 때문에 후위 표기법이 유용하다 (그래서 우리는 우리가 넣어 스택에서 x 및 y 팝 및 스택에 다시 x*y을두고 *를 참조 계산 스택에 x 후 우리는 스택에서 z*y 및 x을 뜨고 당신은 Shunting-yard algorithm를 통해 후위에 중위 표기법에서 변환 할 수 있습니다

스택 붐 귀하의 계산이있다)에 다시 x+(z*y)을두고 + 참조 (위키 백과가 더 잘 설명 내가 할 수있는 것보다)

따라서 수식을 살펴보고 스택에 피연산자를 leaves로 추가하기 때문에 이진 트리를 통해 수식을 쉽게 표현할 수 있습니다. 연산자에 도달하면 스택의 처음 두 노드를 팝하고 운영자를 부모로, 운영자를 자식으로하여 새 노드를 만듭니다. 그런 다음이 나무를 스택 위로 밀어 넣습니다. 방정식이 끝날 때까지 반복하십시오.

Answer 2

이러한 종류의 작업에 사용할 수있는 파싱 라이브러리가 많이 있습니다. pyparsing 등을 사용

:

from pyparsing import * 

def rearrange(tks): 
    T=tks[0] 
    T[0],T[1] = T[1],T[0] 
    return tks 

expr = Forward() 
arithOp = Word("+-*/", max=1) 
terminal = (Word(alphas, alphanums) 
      | Word(nums) 
      | Suppress("(") + expr + Suppress(")")) 
expr << Group(terminal + arithOp + terminal).setParseAction(rearrange) 

parseTree = expr.parseString("x+(y*z)") 
print parseTree 

인쇄 것이다

[['+', 'x', ['*', 'y', 'z']]]