[알고리즘] 스택의 활용 (수식의 괄호 쌍)

• 스택의 대표적인 활용 사례
  • 수식의 괄호 쌍
  • 전위/중위/후외 표기법
  • DFS
  • Flood Fill

수식의 괄호 쌍이란?

• 주어진 괄호 문자열이 올바른지 판단하는 문제.
• 여는 괄호의 갯수와 닫는 괄호의 갯수가 같아야 함. (단, 괄호의 종류가 2개 이상일 경우에는 여는 괄호와 닫는 괄호의 갯수만으로 판별 불가)
• 문자열을 순회하며 닫는 괄호가 나오면 직전의 여는 괄호와 매칭되는지 확인

e.g. 아래의 괄호 문자열이 올바른지 확인하고, 그 이유에 대해 설명하시오.

• ( ( ) ) ( ) ( ) - O. 여는 괄호와 닫는 괄호가 대칭됨.
• ) ) ( ( ) - X. 닫는 괄호와 대칭되는 여는 괄호가 없음.
• ( ) ( ) ) ( ( ) - X. 닫는 괄호와 대칭되는 여는 괄호가 없음.

---

📕 문제 1. ( { ) }

순회를 하며 닫는 괄호가 나오면 스택의 마지막 원소와 비교

target: "(", stack: [] -> 여는 괄호는 스택에 추가 -> stack: ["("]

target: "{", stack: ["("] -> 여는 괄호는 스택에 추가 -> stack: ["(", "{"]

target: ")", stack: ["(", "{"] -> 닫는 괄호는 스택의 마지막 원소 확인, 마지막 원소가 )와 대칭되는 괄호가 아니므로 에러

 

📕 문제 2. ( { }

순회를 하며 스택에 남은 괄호가 있다면 올바르지 못한 괄호 쌍

target: "(", stack: [] -> 여는 괄호는 스택에 추가 -> stack: ["("]

target: "{", stack: ["("] -> 여는 괄호는 스택에 추가 -> stack: ["(", "{"]

target: "}", stack: ["(", "{"] -> 스택의 마지막 원소 확인, 마지막 원소가 }와 대칭되는 괄호이므로 제거 -> stack: ["("]

스택에 괄호가 남아있으므로 올바르지 못한 괄호 쌍이다.

---

💻 연습 문제

바킹독 - 스택의 활용 (수식의 괄호 쌍) 문제집

---

ℹ️ 참고

바킹독 - 스택의 활용 (수식의 괄호 쌍)