스택 - 수식의 괄호쌍

스택 활용

• FloodFill, DFS, 전위/중위/후기 표기법, 괄호쌍

수식의 괄호쌍

• 주어진 괄호 문자열이 올바른지 판단하는 문제

문제 해결을 위한 고찰

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

  ---

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

• 1. 여는 괄호가 나오면 스택에 추가

• 2. 닫는 괄호가 나왔을 경우,
  • 2-1. 스택이 비어있는 경우 = 올바르지 않은 괄호 쌍
  • 2-2. 스택의 top 이 짝이 맞지않는 괄호일 경우 = 올바르지 않은 괄호 쌍
  • 2-3. 스택의 top 이 짝이 맞는 괄호일 경우 pop

• 3. 모든 과정을 끝낸 후 스택에 괄호가 남아있다면 올바르지 않은 괄호쌍,
     남아있지 않다면 올바른 괄호 쌍

  ---

  예시

  ( { }

1. 여는 괄호 ({ 를 스택에 채운다

2. 닫는 괄호 } 를 만났으므로, 가장 최근에 들어온 { 와 비교하면 짝을 이룰 수 있다.

3. 그런데 아직 처리를 못한 ( 가 스택에 남아있다.
   즉, 짝을 지어주지 못한 여는 괄호가 남아있다면 문자열이 올바르지 않은 괄호쌍임을 알 수 있다.

   ( ) }

4. 여는 괄호 ( 를 스택에 채운다

5. 닫는 괄호 ) 를 스택에 가장 최근에 들어온 ) 와 비교하면 짝을 이룰 수 있다.

6. 남은 닫는괄호 } 를 여는 괄호와 매칭해줘야 하는데, 스택에 남는 여는 괄호가 있다.
   즉, 짝을 이루지 못한 닫는 괄호가 존재하므로 문자열이 올바르지 않은 괄호쌍임을 알 수 있다.