[SWEA 1233] 사칙연산 유효성 검사 C++

 

SW Expert Academy

 

 

문제

 

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

아래는 식 “(8/2)*(6-4)”을 이진 트리로 표현한 것이다.

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

 

 

사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진 트리가 주어질 때, 이 식의 유효성을 검사하는 프로그램을 작성하여라.

여기서 말하는 유효성이란, 사칙연산 “+, -, *, /”와 양의 정수로 구성된 임의의 식이 적절한 식인지를 확인하는 것으로, 계산이 가능하다면 “1”, 계산이 불가능할 경우 “0”을 출력한다.

(단, 계산이 가능한지가 아닌 유효성을 검사하는 문제이므로 0으로 나누는 경우는 고려하지 않는다. )

 

 

제약사항

 

총 10개의 테스트 케이스가 주어진다.
총 노드의 개수는 200개를 넘어가지 않는다.
트리는 완전 이진 트리 형식으로 주어지며, 노드당 하나의 연산자 또는 숫자만 저장할 수 있다.
노드는 아래 그림과 같은 숫자 번호대로 주어진다.

 

 

문제풀이

 

트리가 완전 이진 트리 형식으로 주어지기 때문에 트리가 갖는 정점의 총 수를 N이라 했을 때,

N/2번 정점까지는 자식 노드를 가진다.

리프노드는 모두 숫자를 가져야 하고 그 외의 경우에는 연산자를 가지고 있어야 유효한 식이 된다.

 

따라서 식이 유효하지 않은 두 가지가 있다.

 

1. 정점 번호가 N/2 이하일 때, 연산자가 아닌 숫자를 가지는 경우
2. 정점 번호가 N/2보다 클 때, 숫자가 아닌 연산자를 가지는 경우

이 두 가지 경우를 따지면 식이 유효한지, 유효하지 않은지 판별할 수 있다.

 

 

 

C++ 코드