백준 4949 - 균형잡힌 세상

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

4949번: 균형잡힌 세상

풀이

백준 9012번 문제와 유사하지만 이 문제는 (), [] 2개의 괄호가 있고,

각 괄호가 감싸는 문자열 또한 짝이 맞아야 한다.  ([abc)]와 같은 경우는 안 된다.

따라서 현재 스택의 맨 위에 있는 괄호가 ( 인지 [ 인지 확인하는 것이 필요하다.

 

1) 괄호를 입력받으면 스택에 추가한다.

2) 닫는 괄호이면서, 스택이 비어있지 않고, '입력받은 괄호 == 스택의 top에 있는 괄호'라면 스택에서 pop 한다.

3) 닫는 괄호인데 스택이 비어있거나 입력받은 괄호와 짝이 맞지 않다면 false.

4) 문자열의 끝까지 돈 후, 스택이 비어있고 flag가 true라면 true.

 

코드

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool balance(string str)
{
    stack<char> s;
    bool flag = true;
    for(int i=0; i<str.length()-1; i++)
    {
        if(str[i]=='(') s.push(str[i]);
        else if(!s.empty() && str[i] ==')' && s.top()=='(') s.pop();
        else if((s.empty()||s.top()!='(') && str[i] ==')') flag = false;
        else if(str[i]=='[') s.push(str[i]);
        else if(!s.empty() && str[i] ==']' && s.top()=='[') s.pop();
        else if((s.empty() || s.top()!='[') && str[i] ==']') flag = false;
    }

    if(s.empty() && flag == true) return true;
    else return false;
}

int main()
{
    string str;
    while(1)
    {
        getline(cin,str);
        if(str==".") break;

        if(balance(str)) cout<<"yes"<<'\n';
        else cout<<"no"<<'\n';
    }
}