스택의 활용(수식의 괄호쌍)

스택의 활용 범위

• 수식의 괄호쌍
• 전위/중위/후위 표기법
• DFS, Flood Fill

수식의 괄호 쌍

• 말 그래도 "수식의 괄호 쌍" 을 의미.

다음 2가지 예시를 보자.
1. 32 - {6 - (2+4) x 7 ) => { ( ) }
2. 5 + {6 - (12 + 4) x 7) => { ( } )

2번째식은 올바르지 못한 괄호 쌍 (, } 이 들어있다.

이와 같이 수식의 괄호쌍이란 주어진 괄호 문자열이 올바른지 판단하는 문제이다.

문제 해결을 위한 관찰

• 스택을 활용한 방법
  • 1.여는 괄호가 등장하면 스택에 저장한다.
  • 2.저장하다가, 닫는 괄호가 등장하면 스택에 가장 최근에 들어온 여는 괄호와 짝을 이룰 수 있는지 판단한다.
  • 3.스택에 가장 최근에 들어온 여는 괄호를 제거한다.
  • 4.위 과정을 반복한다.

스택을 활용한 문제해결 방법

1. 여는 괄호가 나오면 스택에 추가
2. 닫는 괄호가 나왔을 경우,
   2-1.스택이 비어있으면 올바르지 않은 괄호 쌍
   2-2.스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍
   2-3.스택의 top이 짝이 맞는 괄호일 경우 pop
3. 모든 과정을 끝낸 후 스택에 괄호가 남아있다면 올바르지 않은 괄호 쌍,
   남아있지 않다면 올바른 괄호 쌍

예시

( { ) }

1. 여는 괄호 ( { 를 스택에 채운다.
2. 닫는 괄호 ) 를 만났으므로 스택에 가장 최근에 들어온 여는 괄호 ) 와 짝을 짓는다. 그런데 둘은 짝이 안되므로 이 문자열이 올바르지 않은 괄호 쌍임을 알 수 있다.

( { }

1. 여는 괄호 ( { 를 스택에 채운다.
2. 닫는 괄호 } 를 만났으므로 가장 최근에 들어온 { 와 비교하면 짝을 이룰 수 있다.
3. 그런데 아직 처리를 못한 ( 가 스택에 남아있다.
   즉, 짝을 지어주지 못한 여는 괄호가 남아있다면 문자열이 올바르지 않은 괄호쌍임을 알 수 있다.

( ) }

1. 여는 괄호 ( 스택에 채워주고 ) 와 비교하면 짝을 이룰 수있다.
2. 남아있는 괄호 } 를 여는 괄호와 매칭해줘야 하는데 스택에 남는 여는 괄호가 없다.
   즉, 짝을 이루지 못한 닫는 괄호가 존재하므로 문자열이 올바르지 않은 괄호쌍임을 알 수 있다.