표현식 트리
표현식 트리는 리프 노드에 연산할 값이 있고 내부 노드에는 리프 노드가 수행될 연산자가 포함되어 있습니다.
예
4 + ((7 + 9) * 2) 다음과 같은 표현식 트리가 있습니다.
표현식 트리를 구성하는 알고리즘
T를 표현식 트리라고 하자.
If T is not NULL:
If T->data is an operand:
return T.data
A = solve(T.left)
B = solve(T.right)
--> Calculate operator for 'T.data' on A and B, and call recursively,
return calculate(A, B, T.data)
표현식 트리를 구성하는 방법은 무엇입니까?
주어진 표현식에 대한 표현식 트리를 구성하기 위해 일반적으로 스택 데이터 구조를 사용합니다.
처음에 우리는 주어진 접미사 표현식을 반복하고 아래와 같이 단계를 따릅니다 -
- 주어진 표현식에서 피연산자를 얻으면 스택에 푸시합니다. 표현 나무의 루트가 됩니다.
- 연산자가 표현식에서 두 개의 값을 가져오면 표현식 트리를 자식으로 추가하고 현재 노드에 푸시합니다.
- 주어진 표현식을 완성하지 않을 때까지 1단계와 2단계를 반복합니다.
- 이제 모든 루트 노드에 피연산자만 포함되어 있고 모든 하위 노드에 값만 포함되어 있는지 확인합니다.