산술 표현식에서 첫 번째 연산자를 찾는 방법은 무엇입니까?

Question

이 산술 표현식은 E=((c+(a*b))-(c+(d*e)))입니다. 이 예는 '-' 때문이다
나는 첫 번째 노드를 만들기 위해, 내가 처음 연산자를 찾을 필요가 재귀 함수

typedef struct node { char info; struct node*left, *right; } TNode, *Tree; 
Tree fBuild (char *E) // recursive function 
Tree aux = (Tree)malloc (sizeof(TNode)); //tree in recursive function 

첫째로 이진 트리에 넣어하는 최초의 연산자를 찾을 필요가 나는 재귀와 함께 한 후에

  - 

    /  \ 
    /  \ 
    +   + 
/ \  /\ 
c  *  c * 
    /\  /\ 
    a b  d  e 

가 어떻게 셀 수 E2=(c+(d*e))

예와 E1=(c+(a*b))와 aux->left 및 aux->right을위한 기능 괄호 또는 다른 알고리즘은 C 코드에서 첫 번째 연산자를 찾으려면?

Answer 1

표준 연습 도구 lec, yacc 및 Shunting yard algorithm과 같은 표준 알고리즘을 사용할 수 없으므로 프로그래밍 연습이라고 가정합니다.

맨 위의 빼기 기호를 찾는 방법에 대해 질문합니다. 그 괄호를 세는 것. 각 대괄호에 대해 하나씩 추가하고 각 대괄호에 대해 하나씩 빼십시오. 이 예제에서 -은 1의 카운트를 갖는 유일한 연산자입니다. C에서 문자열 s가 있다고 가정합니다. C에서는 문자열의 문자를 통해 간단한 루프가됩니다.

나무를 만드는 가장 효율적인 방법은 아닙니다. 한 번에 입력 한 문자를 스캔하여 부분 나무를 구성하고 깊이를 추적 할 수 있습니다.

Answer 2

일반적인 해결 방법은 재귀 적 하향 파서와 같은 구문 분석 기법을 사용하여 트리를 작성하는 것입니다.

문법에 암시 적으로 조작 순서를 지정할 수 있습니다.

Expression :== Term | Expression ('+' | '-') Term 
Term :== Factor | Term ('*' | '/') Factor 
Factor :== value | '(' Expression ')' 

왼쪽 재귀를 피하기 위해 문법을 약간 재정렬해야합니다. 일단 그렇게하면 입력의 현재 위치를 가져 와서 새 트리 노드를 반환하는 문법 규칙 (예 : ParseExpression, ParseTerm 및 ParseFactor)에 대한 함수를 작성하여 재귀 적 강하 문법을 작성할 수 있습니다.

입력의 시작 부분과 함께 ParseExpression을 호출하여 파서를 시작하면 트리의 루트 노드가 다시 나타납니다.