백준 4949: 균형잡힌 세상 (C++)

문제 링크: www.acmicpc.net/problem/4949  

4949번: 균형잡힌 세상

 

스택을 활용한 문제이다. 

여는 괄호가 나왔을 때 스택에 넣어주고, 닫는 괄호가 나왔을 때 스택의 top(제일 최근에 들어간 여는 괄호)와 짝이 맞는지 확인한다. 짝이 맞지 않으면 flag를 false로 바꾸고 반복문을 탈출한다.

짝이 맞지 않는 경우가 없었어도 마지막에 여는 괄호만 나오고 닫는 괄호가 나오지 않았으면 올바른 문자열이 아니다. 이 경우 스택에 원소가 남아있다.

flag가 false인 경우와 스택에 원소가 남아있는 경우 "no"를 출력하고 아닌 경우 "yes"를 출력한다.

 

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

int main() {
	string str;
	stack<char> st;

	while (true) {
		getline(cin, str);

		// 입력 종료 조건
		if (str == ".") {
			break;
		}

		// 스택 초기화
		while (!st.empty()) {
			st.pop();
		}

		bool flag = true;
		for (int i = 0; i < str.length(); i++) {
			// 여는 괄호 만나면 스택에 넣기
			if (str[i] == '(' || str[i] == '[') {
				st.push(str[i]);
			}
			else if (str[i] == ')') {
				if (!st.empty() && st.top() == '(') {
					st.pop();
				}
				else {
					flag = false;
					break;
				}
			}
			else if (str[i] == ']') {
				if (!st.empty() && st.top() == '[') {
					st.pop();
				}
				else {
					flag = false;
					break;
				}
			}
		}

		if (flag && st.empty()) { // 스택이 비어있어야 한다
			cout << "yes\n";
		}
		else {
			cout << "no\n";
		}
	}

	return 0;
}