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

수식의 괄호 쌍이란?

 

수식의 괄호 쌍: 주어진 괄호 문자열이 올바른지 판단하는 문제

 

 

문제 해결을 위한 관찰

 

 

문제 해결 방법

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

2. 닫는 괄호가 나왔을 경우,

    2-1. 스택이 비어있으면 올바르지 않은 괄호쌍

    2-2. 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍

    2-3. 스택의 top이 짝이 맞는 괄호일 경우 pop

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

남아있지 않으면 올바른 괄호 쌍

 

 

연습문제

4949번: 균형잡힌 세상 (acmicpc.net)

 

 

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  while(true){
    string a;
    getline(cin, a);
    if(a == ".") break;
    stack<char> s;
    bool isValid = true;
    for(auto c : a){
      if(c == '(' || c == '[') s.push(c);
      else if(c == ')'){
        if(s.empty() || s.top() != '('){
          isValid = false;
          break;
        }
        s.pop();
      }
      else if(c == ']'){
        if(s.empty() || s.top() != '['){
          isValid = false;
          break;
        }
        s.pop();
      }
    }
    if(!s.empty()) isValid = false;
    if(isValid) cout << "yes\n";
    else cout << "no\n";
  }
}

 

 

 

 

 

 

출처

BaaaaaaaarkingDog | [실전 알고리즘] 0x08강 - 스택의 활용(수식의 괄호 쌍) (encrypted.gg)