[백준 알고리즘/C++/스택] 9012 괄호

 

 

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다

그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다

만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다

예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다

입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내는 문제

 

 

'( ' (방시혁..?) 이게 입력되면 스택에 저장

' )' 이게 입력되면 스택에서 하나를 pop하면 된다

empty라 pop이 불가능하거나 마지막에 스택이 empty가 아니라면 NO를 출력한다

 

 

#include <iostream>
#include <stack>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    string ps;
 
    cin >> n;
    while (n--) {
        cin >> ps;
 
        stack<char> s;
        for (int i = 0; i < ps.size(); i++) {
            if (ps[i] == '(')
                s.push('(');
            else {
                if (s.empty()) {
                    s.push('x'); //임의로 넣어서 NO 출력 유도
                    break;
                }
                else
                    s.pop();
            }
        }
 
        if (!s.empty())
            cout << "NO" << "\n";
        else
            cout << "YES" << "\n";
    }
}