파서 트리 또는 표현식 트리

Question

저는 명령 행 계산기를하고 있습니다. 그래서 표현식을 파싱해야합니다.

calc 2*(3+4)*5 

이미 스캐너 단계가 완료되어 토큰의 배열을 반환했습니다. 이제 구문 분석기 단계에 있습니다. 그러나 파서/표현 트리를 수행하는 방법에 대한 단서가 없습니다. 이 모든입니다

지금까지이 : 내 나무는 단지 왼쪽으로 인상 볼 수 있듯이

while (*tokens != 0) { 
    NODE* n = create_node(*tokens++); 
    insert_node(&root, &n); 
} 

:

NODE* create_node(TOKEN* t) { 
    NODE* n = (NODE*)malloc(sizeof(NODE)); 
    n->t = t; 
    n->l = n->r = 0; 
    return n; 
} 

void insert_node(NODE** top, NODE** n) { 
    if (!*top) { 
     *top = *n; 
     return; 
    } 

    if (!(*top)->l) insert_node(&(*top)->l, n); 
    else 
    if (!(*top)->r) insert_node(&(*top)->r, n); 
    else 
     insert_node(&(*top)->l, n); 
} 

그런 다음 내가 좋아하는 토큰 배열을 전달합니다. 나는 최상위에있는 연산자에 의해 순서를 매기는 방법과 연산자 우선 순위를 포함하여 숫자를 잎으로 만드는 방법에 대한 단서가 없다.

계몽주의와 프로그래밍 (코드) 용어로도 감사하겠습니다.

Answer 1

노드 생성을위한 코드가 괜찮아 보입니다. 문제는 이진 트리를 올바르게 빌드하는 방법을 알아내는 코드가 필요하다는 것입니다. 널 포인터가있는 곳이면 어디서든 노드를 고수 할 수 없습니다.

귀하의 예를 발현 : 2*(3+4)*5

이 같은 변신합니다 :

* 
/\ 
    * 5 
/\ 
2 + 
/\ 
    3 4 

선생님이 당신에게이 작업을 수행하는 방법을 몇 가지 아이디어를 제공해야합니다.

제가 대학에있을 때, 저는 이런 종류의 코드를 작성했으며, 우리는 우리 자신의 "재귀 적 하강 파서"를 작성했습니다. 또 다른 인기있는 접근법은 GNU Bison과 같은 시스템을 사용하는 것입니다.

메모를 검토하고 선생님이 이에 대해 이야기 한 내용을보고 정말로 모르는 경우 교사에게 질문해야합니다.

http://en.wikipedia.org/wiki/GNU_bison

Answer 2

http://en.wikipedia.org/wiki/Recursive_descent_parser

@Fabricio : 힌트. 입력 (중위 표현식)을 후위 또는 접두사 표현식으로 변환 해보십시오. 변환 할 때 토큰을 스택으로 밀어 넣으십시오. 각 튜플 (하나의 연산자와 두 개의 피연산자)을 팝하여 결과를 평가하고 결과를 스택에 푸시합니다. 스택이 비어있을 때까지 반복하십시오. 연산자 우선 순위를 쉽게 적용 할 수 있도록 입력 표현식에 중괄호를 추가 할 수 있습니다 (단점을 감안할 때나 자신의 교수를 설득해야 함).

Answer 3

언급 된 바와 같이 스택을 사용

An infix to binary-expression-tree parser

모두 구현

An infix to postfix parser

의 C++ 구현이 링크를 참조하십시오. 중위 표현식 트리에서 이진 표현 트리의 경우 두 개의 스택이 사용됩니다. 하나는 연산자 용이고 다른 하나는 피연산자 용입니다.