[백준(BOJ) 4949번] 균형잡힌 세상 (C++)

문제 링크

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

 

문제 정보

입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

 

풀이

 스택을 활용하여 수식의 괄호 쌍 문제를 해결 할 수 있다. 수식의 괄호 쌍 알고리즘은 블로그 내 글을 통해 확인할 수 있다. 

- 스택의 활용(수식의 괄호 검사)

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	while (true) {
		string str;
		getline(cin, str);
		
		if (str == ".") {
			break;
		}
		
		stack<char> S;
		bool isValid = true;
		
		for (auto c : str) {
			if (c == '(' || c == '[') {
				S.push(c);
			} else if (c == ')') {
				if (S.empty() || S.top() != '(') { // 올바르지 않은 괄호 쌍
					isValid = false;
					break;
				}
				S.pop();
			} else if (c == ']') {
				if (S.empty() || S.top() != '[') { // 올바르지 않은 괄호 쌍
					isValid = false;
					break;
				}
				S.pop();
			}
		}
		
		if (!S.empty()) { // 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않음!
			isValid = false;
		}
		
		if (isValid) {
			cout << "yes" << '\n';
		} else {
			cout << "no" << '\n';
		}
	}
	
	return 0;
}