알고리즘
[알고리즘] 스택의 활용 (수식의 괄호 쌍)
rubato.dev
2025. 7. 21. 12:59
- 스택의 대표적인 활용 사례
- 수식의 괄호 쌍
- 전위/중위/후외 표기법
- 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: ["("]
스택에 괄호가 남아있으므로 올바르지 못한 괄호 쌍이다.
💻 연습 문제
ℹ️ 참고