이진트리 계산

소개글

1. 문제 인식
① 사용자로부터 산술식을 입력받습니다.
② 중위순위로 만들어 출력합니다.
③ 입력받은 산술식을 계산하여 출력합니다.

목차

1. 문제 인식

2. 문제 접근 방법 및 분석

3. 소스코드 및 주석

4. 결과화면

5. 느낀점

본문내용

1. 문제 인식
① 사용자로부터 산술식을 입력받습니다.
② 중위순위로 만들어 출력합니다.
③ 입력받은 산술식을 계산하여 출력합니다.

2. 문제 접근 방법 및 분석
①입력형태
사용자로부터 중위식으로 입력받을 경우 왼쪽부터 차례대로 읽으면 되지만 계산시 신경써야 할 부분이 많아 이진형태로 입력받기로 하였습니다. 트리의 이진형태로 입력받기 위해 사용자로부터 왼쪽 이진트리를 입력받은후 오른쪽 이진트리를 입력받도록 하였습니다. 순환함수를 사용하여 루트에 넣고 순환을 반복하여 올바른 식인지 확인하여 트리노드를 생성 및 연결을 합니다.
(1*(4/2))를 계산하고 싶다면 *(1,/(4,2))를 입력해야 합니다.

②중위순회
중위순회는 왼쪽 포인터가 가리키는 곳을 재귀적으로 먼저 중위 순회한후 노드를 방문합니다. 그후 오른쪽 포인터가 가르키는 곳을 중위 순회한다. 중위순회를 할 경우 중위식과 같아야합니다. 트리를 출려하기 위해 루트와 왼쪽 서브트리와 오른쪽 서브트리를 전부 출력해야합니다. 중위순회를 이용하여 출력을 하였으며 왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 포인터를 이동하면서 출력을 하게 되면 루트로 다시 올라가야 하는 포인터 정보를 가지고 있습니다.

③후위 순회
후위 순회는 왼쪽 포인터가 가리키는 곳을 재귀적으로 먼저 후위 순회합니다. 그후 오른쪽 포인터가 가리키는 곳을 마지막으로 노드를 방분합니다. 계산알고리즘으로 쓰이는데 계산은 트리에서 단말노드의 숫자를 스택에 넣고 그 단말노드의 서브루트의 연산자를 이용해 꺼내어 계산하고 다시 스택에 넣는 과정을 되풀이합니다. 트리의 모든 노드를 순회하게 되면 스택에 남아있는 단 하나의 값이 계산 결과가 되는 것입니다.

참고 자료

없음