[C++] BAEKJOON 4949 균형잡힌 세상

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

일반적으로 스택를 써서 올바른 괄호를 체크하는 문제에서 괄호의 종류를 늘려 약간의 응용이 필요한 문제였습니다.

입력

string s;
getline(cin, s);

입력은 띄어쓰기가 포함된 문장이기 때문에 getline 을 이용해서 받았습니다.

올바른 괄호 확인

하나의 스택를 사용하여 두 괄호의 유효성을 확인해줄 수 있습니다. 아래와 같은 알고리즘으로 이를 확인합니다.

• ( 나 [ 가 들어올 경우에는 스택에 담아줍니다.

• ) 가 들어왔을 경우에는 아래 두 가지 조건을 확인합니다.

  • 스택이 비어있다면 false
  • 스택의 마지막 값이 ( 가 아니라면 false

  두 가지 조건에 문제가 없다면, 마지막은 ( 라는 의미입니다. () 짝이 맞았으므로 스택에서 ( 를 pop 하여 줍니다.

• ] 가 들어왔을 경우에는 아래 두 가지 조건을 확인합니다.

  • 스택이 비어있다면 false
  • 스택의 마지막 값이 [ 가 아니라면 false

  두 가지 조건에 문제가 없다면, 마지막은 [ 라는 의미입니다. [] 짝이 맞았으므로 스택에서 [ 를 pop 하여 줍니다.

• 마지막으로 스택이 차있다면 false, 그렇지 않으면 true

 

#include <iostream>
#include <stack>

using namespace std;

int main(){
    while (1){
        stack <char> st;
        string s;
        getline(cin, s);
        
        if (s=="."){
            break;
        }
        int flag = 0;
        for (int i=0;i<s.size();i++){
            char c = s[i];
            if (c == '(' || c=='['){
                st.push(c);
            }
            else if (c == ')'){
                if (st.empty() || st.top()!='('){
                    flag = 1;
                    break;
                }
                st.pop();
            }
            else if (c == ']'){
                if (st.empty() || st.top()!='['){
                    flag = 1;
                    break;
                }
                st.pop();
            }
        }
        
        if (flag || !st.empty()) cout << "no\n";
        else cout << "yes\n";
        
    }
    
    return 0;
    
}