BOJ 4949 균형잡힌 세상

사용한 알고리즘

스택

알고리즘 설명

한줄씩의 스트링을 받는다.
스트링에 앞에서 부터 읽어가면서 ( 또는 [이 나오면 스택에 이 케릭터를 푸쉬한다.
) 또는 ]가 나오면 스택에서 하나씩 뽑는다.
Case1. 뽑았을때, ")"이면 스택에서 뽑힌 케릭터 "("
Case2. 뽑았을때, "]"이면 스택에서 뽑힌 케릭터 "["
Case3. 스택이 비어있거나, 위 Case1,2가 아닌경우 "no"
스트링이 위를 케이스에 걸리지 않으면 “yes”를 출력한다.

풀이

// baekjoon 4949 yechan
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
const int MAX_N=111;

char S[MAX_N];

int main() {
	while (1) {
		scanf("%100[^\n]s", S);
		getchar();
		if (S[0] == '.' && strlen(S) == 1) break;
		stack<char> st;
		bool flag = true;
		for (int i=0; S[i]; i++) {
			if (S[i] == '(' || S[i] == '[') {
				st.push(S[i]);
			}
			if (S[i] == ')') {
				if (st.empty() || st.top() != '(') {
					flag=false;
					break;
				}
				st.pop();
			}
			if (S[i] == ']') {
				if (st.empty() || st.top() != '[') {
					flag=false;
					break;
				}
				st.pop();
			}
		}
		if (!st.empty()) flag=false;
		printf("%s\n", flag ? "yes" : "no");
	}
	return 0;
}