9.3.5 수식 파서 트리 구현

이번에는 수식 파서 트리를 구현하기로 해요.

수식 파서 트리에서는 어휘 분석기에서 생성한 토큰 컬렉션에 있는 토큰들을 파서 트리에 매달 것입니다. 이에 토큰 컬렉션을 멤버 필드로 선언하세요.

노드를 Parser 클래스 내부에 구조체로 정의합시다. private 가시성 영역이므로 Parser 클래스 외부에서는 노드 구조체 형식을 사용할 수 없어 신뢰성을 높일 수 있어요.

루트를 기억할 멤버가 필요하겠죠.

생성자에서는 토큰 컬렉션을 입력 인자로 받습니다.

파서 트리에 파싱하는 메서드를 제공합시다.

후위 표기로 출력하는 메서드도 제공합시다.

계산하는 메서드를 제공합시다.

내부적으로 토큰을 파서 트리에 매다는 메서드가 필요합니다.

후위 표기로 출력하기 위해 후위 순회하는 메서드가 필요합니다.

계산할 때도 후위 순회하며 계산합니다.

소멸할 때 동적으로 생성한 모든 노드를 소멸해야겠죠.

Parser 클래스의 소스 코드를 구현합시다. 먼저 생성자에서는 입력 인자로 받은 컬렉션을 멤버 필드에 설정하세요.

소멸자에서는 Clear 메서드를 호출하여 모든 노드를 소멸합니다.

모든 노드를 소멸할 때 후위 순회로 소멸해야 합니다.

파싱하는 메서드를 구현합시다.

먼저 토큰 개수를 구하세요.

첫 번째 토큰으로 노드를 생성하여 root에 설정하세요.

반복해서 모든 토큰을 파서 트리에 추가하세요.

토큰을 파서 트리에 매다는 메서드를 구현합시다.

먼저 입력 인자로 받은 토큰을 입력 인자로 노드를 생성하세요.

루트의 토큰을 구하세요.

루트의 토큰의 우선 순위가 추가할 토큰의 우선 순위보다 크거나 같은지 판별하세요.

예를 들어 추가할 노드의 기호가 더하기나 빼기 기호일 때는 현재 루트에 있는 토큰들은 새로운 노드의 왼쪽 피연산자로 들어가야 합니다. 그리고 루트는 now로 변경해야겠죠.

다음은 root의 토큰 우선 순위가 추가할 토큰의 우선 순위보다 크거나 같을 때 링크를 조절하는 과정을 논리적으로 도식한 것입니다.root의 토큰 우선 순위가 추가할 토큰의 우선 순위보다 크거나 같을 때 링크를 조절하는 과정

root의 토큰 우선 순위가 추가할 토큰의 우선 순위보다 작을 때는 새로 추가하는 노드가 피연산자일 때와 연산자일 때 코드가 조금 다릅니다.

연산자일 때는 새로운 노드의 왼쪽 자식으로 루트의 오른쪽 자식을 매달고 루트의 오른쪽 자식에 새로운 노드를 매답니다.

다음은 root의 토큰 우선 순위가 추가할 토큰의 우선 순위보다 작으면서 연산자일 때 링크를 조절하는 과정을 논리적으로 도식한 것입니다.root의 토큰 우선 순위가 추가할 토큰의 우선 순위보다 작으면서 연산자일 때 링크를 조절하는 과정

새로 추가할 토큰이 피연산일 때는 루트에서 오른쪽 자식이 없는 노드를 찾아서 매답니다.

다음은 root의 토큰 우선 순위가 추가할 토큰의 우선 순위보다 작으면서 피연산자일 때 링크를 조절하는 과정을 논리적으로 도식한 것입니다.root의 토큰 우선 순위가 추가할 토큰의 우선 순위보다 작으면서 피연산자일 때 링크를 조절하는 과정

후위 순위로 출력하는 메서드를 구현하세요.

계산하여 결과를 반환하는 메서드를 구현하세요.

여기에서 구현할 수식 파서 트리에서 모든 노드는 자식이 둘이거나 없습니다. 연산자는 자식이 둘 있고 피연산자는 자식이 없습니다. 따라서 왼쪽 자식이 있다는 것은 연산자를 의미합니다. 먼저 왼쪽 서브 트리를 계산하세요. 그리고 오른쪽 서브 트리를 계산합시다.

현재 토큰을 연산자 토큰으로 변환하세요.

그리고 연산 후에 결과를 반환하세요.

피연산자일 때는 값을 반환합니다.