올바른 괄호 문자열 검사하기 : 스택으로 손쉽게 해결해 보자.

 저번 시간에 스택을 배웠으니까, 응용 문제들을 다뤄보도록 하겠습니다. 오늘은 조금 쉬운, 올바른 괄호 문자열을 검사하는 알고리즘을 작성해 보겠습니다. 올바른 괄호 문자열은 다음과 같이 재귀적으로 정의됩니다. 빈 문자열은 valid하다. (괄호문자열) 역시 valid 하다. 괄호문자열에 괄호문자열을 concat 한 것도 valid 하다.

 

 예를 들어서 ()(())은 valid 합니다. 하지만, ())이나, ()((은 valid하지 않습니다. 이것은 어떻게 구현하면 좋을까요?

 

 

---

 먼저, "())"이 올바른지 판단해 보도록 하겠습니다.

 

 

 '('이 들어오면, 괄호 스택에 (을 push 합니다. '('이 들어왔기 때문에, 스택에 '('가 들어가 있습니다.

 

 

 그 다음에는 ')'가 옵니다. 이 때에는 stack의 맨 위의 원소를 보는데요. '('가 있습니다. 괄호 쌍이 맞습니다. '(' 와 맞는 괄호쌍은 ')'입니다. 즉, 닫는 괄호가 들어오고, 쌍이 맞았다면, 스택에서 맨 위의 원소만 pop 합니다. 맨 위의 원소를 제거한 후에, stack은 비어 있습니다.

 

 

 

 이 때, ')'가 다시 들어옵니다. 맨 위에는 아무 것도 없는데, 맨 위에 있는 원소를 꺼내 오려고 합니다. valid 하지 않아요. 즉, ')' 연산이 들어왔을 때, 스택이 비어 있는 경우, 올바른 괄호 문자열이 아닙니다.

 

 

---

 다음에 "()(("가 올바른 괄호 문자열인지 판단해 보도록 합시다.

 

 

 먼저 '('를 읽습니다. 여는 괄호이기 때문에, 스택에 '('이 들어갑니다.

 

 

 이제 ')', 닫는 것을 읽었습니다. 일단 맨 위에 원소가 있는지 봅시다. '('를 read 했습니다. '('는 ')'과 쌍이 맞습니다. 따라서, 맨 위에 있는 원소를 pop 하고 계속 진행합니다.

 

 

 문자열의 3번째에 있는 문자는 '('입니다. 여는 것이 나왔기 때문에, 스택에 push 합니다.

 

 

 그러면 이 상태가 됩니다. 4번째에 있는 문자 또한 '(' 이므로, push 합니다.

 

 

 string에 있는 요소들을 다 읽었습니다. 다 읽었는데, 스택에 값이 있습니다. 이 때도 올바르지 않습니다. 즉, 모든 문자를 다 읽었을 때, 스택이 비어 있지 않으면 invalid 합니다.

 

 

---

 만약에 ()(())라면 어떨까요? ()((까지는 같으니까, 5번째 문자인 ')'를 읽었을 때 어떤 일이 발생하는지부터 보면 되겠습니다. 일단, 5번째 문자를 읽었을 때, 스택의 맨 위에 있는 문자를 가지고 와야 하는데요.

 

 

 맨 위에 있는 것이 '('입니다. 이것은, 제가 읽은 닫은 괄호인 ')'과 쌍이 맞습니다. 따라서, 맨 위에 있는 것을 제거합니다. 만약에 읽은 문자가 '}'이였다면, 스택의 맨 위에 있었던 '('과 맞지 않았을 겁니다. 쌍이. 그러면 그 때 올바른 것이 아니다. 라고 바로 출력해 버리면 됩니다.

 

 

 6번째 문자는 ')'이였습니다. 그렇기 때문에, 맨 위에 있는 원소를 가지고 옵니다. '('는 제가 읽은 문자인 ')'과 쌍이 맞기 때문에, 스택의 맨 위에 있는 원소를 제거하면 됩니다.

 

 

 다 돌고 나서 보니까, stack이 비어 있습니다. 따라서, "(())()"는 valid한 괄호 문자열이라고 할 수 있어요.

 

 

---

 이제 코드를 봅시다.

 

 

 스택에서 중요한 것은 꼭대기, 그러니까 맨 위에 있는 원소를 가리키는 포인터라고 했습니다. 저는 이것을 top으로 두었습니다. 초기에는 stack이 비어 있기 때문에, top을 -1로 초기화 해 주었습니다. 그리고, 문자열의 길이는 최대 50이므로, 크기를 51로 잡아놓았습니다.

 

 

 그러면, push 연산이 일어날 때, top을, 그러니까 맨 위를 가리키는 포인터를 하나 증가시키고, 그 자리에 원소를 넣으면 됩니다. _top은 맨 위에 있는 원소를 가지고 오는 연산인데요. top이 가리키는 곳을 가지고 오면 됩니다. 단, top이 0보다 작은 경우, 비어 있는 것이므로, 그 때에는 -1이라던지 0과 같이 찾을 수 없다. 는 정보를 리턴합니다.

 

 pop을 할 경우에는, 현재 top pointer가 0보다 작은지 검사해야 하는데요. 만약에 스택이 비어있다면 top의 값이 0보다 작을 겁니다. 따라서, -1을 리턴합니다. 그렇지 않다면, top의 값을 하나 감소시키고 0을 리턴합니다.

 

 

 '('이 들어온 경우, push를 해 주었습니다. 그 전에 s[0]이 '('인지를 검사해 주었는데요. 만약에 s[0]의 값이 '('가 아니라면 invalid 합니다. 만약에 괄호가 (, {, [, ], }, ) 이렇게 6개가 나오면, 20번째 줄도 바뀌어야 할 겁니다. s[0]이 '('이거나, '{'이거나, '['이라면 올바른 괄호 문자열일 수 있고, 그게 아니라면 닫는 것이 먼저 나오니까 무조건 invalid 하다는 것.

 

 초반에 이렇게 컷팅을 잘 해 주시면 좋습니다.

 

 

 다음에, ')'이 나오면, 맨 위에 있는 원소가 '('인지 검사합니다. 만약에 그렇지 않다면, invaild 하다는 표시를 합니다. 이렇게 다 수행하고 나서 스택이 비어있지 않다면 어떻게 될까요? 예를 들어서 "((((((" 이런 문자열은 다 수행하고 나서, 스택에 원소가 6개나 들어가 있을 겁니다.

 

 이런 경우 유효한 괄호 문자열이 아닙니다. 따라서, invalid하다고 해야 하는데, 44번째 줄에서 그러한 일을 하고 있습니다. 이렇게 하시면 무난하게 검사를 하실 수 있을 듯 싶습니다.