수식연산 (트리)

알고리즘 및 문제풀이 (1) 입력 알고리즘 순환함수로 사용하여 처음 루트를 넣고 계속 순환을 하면서 식이 올바른지를 검사하며 트리노드를 생성 및 연결을 합니다. 트리노드의 자료는 문자형 연산자와 실수형 수가 들어가게 되는데 공용체와 불린형 tag를 사용하여 트리노드의 자료를 구분하였습니다. (2) 출력 알고리즘(중위 순회) 트리를 출력하기 위해선 루트와 왼쪽 서브트리와 오른쪽 서브트리를 전부 출력해야합니다. 예를 들어 왼쪽서브트리->루트->오른쪽서브트리 순서로 포인터를 이동하면서 출력을 하게 되면 루트로 다시 올라가야 하는 포인터 정보를 가지고 있어야 됩니다. 순환적 알고리즘은 포인터 정보가 없어도 함수를 불렀다가 내부시스템 스택에 의하여 저절로 루트로 복귀하게 됩니다. 알고리즘 시간계산량이 많아지겠지만 간단하기 때문에 사용하였습니다. (3) 계산 알고리즘(후위 순회) 계산은 트리에서 단말노드의 숫자를 스택에 넣고 그 단말노드의 서브루트의 연산자를 이용해 꺼내어 계산하고 다시 스택에 넣는 과정을 되풀이합니다. 트리의 모든 노드를 순회하게 되면 스택에 남아있는 단 하나의 값이 계산 결과가 되는 것입니다.