[SWEA 1232] 사칙연산 C++

 

SW Expert Academy

 

 

문제

 

사칙연산으로 구성되어 있는 식은 이진 트리로 표현할 수 있다. 

아래는 식 "(9/(6-4))*3"을 이진 트리로 표현한 것이다.

임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽 서브 트리의 결과와 오른쪽 서브 트리의 결과를 사용해서 해당 연산자를 적용한다.

 

 

사칙연산 "+, -, *, /"와 양의 정수로만 구성된 임의의 이진트리가 주어질 때, 이를 계산한 결과를 출력하는 프로그램을 작성하라.

 

 

 

제약사항

정점의 총 수 N은 1≤N≤1000.

 

 

문제풀이

 

tree 배열을 2차원으로 선언해서 연산자 or 숫자, 왼쪽 자식, 오른쪽 자식 정보를 저장해주었다.

연산자일 경우 +는 -1, -는 -2, *는 -3, /는 -4로 숫자와 구분되는 값으로 바꿔주었다.

 

 

루트인 1부터 시작해서 tree[v][0]이 0보다 작은 경우, 즉 연산자인 경우에는 왼쪽 서브 트리, 오른쪽 서브 트리를 먼저 방문하여 각 서브 트리의 계산 결과를 구한다.

그런 다음 왼쪽 서브 트리 값과 오른쪽 서브 트리 값을 해당 연산자에 따라 계산해준다.

tree[v][0]이 0보다 큰 경우, 즉 숫자인 경우에는 tree[v][0]을 리턴해준다.

 

 

c++ 코드