백준 9012번, 괄호

백준 9012번 c++ 문제풀이

문제:

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다.
그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

풀이:

1. ’)’ 일 때는 stack이 비워져 다면 break 하고 “NO” 출력
2. ’(‘ 일 때는 문자열 마지막인지 확인하고 마지막으면 “NO” 출력
3. ’(‘ 이 마지막이 아니라면 stack에 push한다.
4. 위의 과정을 다하고 나서 stack이 empty라면 “YES” 출력한다.
5. 반복문이 끝나면 다음 문자열의 결과를 확인하기 위해 stack을 초기화한다.

코드:

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;
stack <char> s;

int main(){
    int n;
    cin >> n;

    for(int i=0;i<n;i++){
        string input;
        int len = 0;

        cin >> input;
        len = input.length();
        while( !s.empty() ) 
        {
            s.pop();
        }
        for(int j=0;j<len;j++){   
            if(input[j] == ')'){ 
                if(s.empty()){
                    cout << "NO\n";
                    break;
                }
                else if(s.top() == '('){
                    s.pop();
                    if(j==len-1){
                        if(s.empty()){
                            cout << "YES\n";
                        }else{
                            cout << "NO\n";
                        }
                    }
                }
            }
            else if(input[j] == '('){ 
                if(j == (len - 1)){
                    cout << "NO\n";
                    break;
                }else{
                    s.push(input[j]);  
                }
            }
        }
    }
    return 0;
}

감사합니다.