16637. 괄호 추가하기

16637번: 괄호 추가하기

---

C언어에서 문자열 처리를 배울 때 흔히 연습하는 사칙연산 문제이다. 문제에서 연산자의 우선순위는 모두 동일하다고 하였으므로 기본적으로 왼쪽에서부터 하나씩 계산해야 한다.

괄호 추가

이제 괄호를 추가해 보자. 괄호 안에는 하나의 연산자만 들어가야 하며, 괄호를 중첩해서 사용할 수는 없다. 직관적으로는 매우 이해하기 쉬운 조건이지만, 의외로 구현하기에는 까다로울 수 있다. 엄밀하게 과정을 정의하면 다음과 같다.

 

• 연산자의 양 옆 피연산자를 괄호로 묶어야 한다.

당연한 사실이지만 엄밀한 정의를 위해 추가하였다. 

 

• $i$번째 연산자를 괄호로 묶으면, $i+1$번째 연산자는 괄호로 묶을 수 없다.

괄호를 중첩해서 사용할 수 없기 때문이다. 예를 들어 $((3+4)*2)+7$은 불가능한 식이다. 첫 번째 연산자 $+$를 괄호로 묶었으므로, 두 번째 연산자 $*$를 괄호로 묶어서는 안 된다.

구현

이제 코드를 구현해 보자. 계산식에 괄호를 전부 추가한 후 후위식 계산을 구현해도 되지만, 이 문제에서는 그렇게까지 하지 않아도 된다. 연산자의 우선순위가 없기 때문이다. 16638번(연산자의 우선순위가 있음)를 풀려면 후위식을 구현해야겠지만.

 

계산 과정에서 주의할 점은, 연산자의 우선순위가 오로지 괄호에 의해서만 결정된다는 점이다. 따라서 왼쪽에서부터 차례대로 계산하되, 괄호로 묶인 연산자를 먼저 계산하는 방법으로 구현할 수 있다.

---

의외로 구현하기 힘들었던 문제. 괄호를 문자열에 직접 추가하려다가 개고생했다..