19.4 짝이 맞지 않는 괄호

이 책의 19장은 스택, 큐 등에 관한 내용입니다. 유명한 자료구조이고 해당 내용 중 스택의 대표 문제인 괄호 문제를 풀어보겠습니다.

 

문제는 간단합니다. 괄호가 제대로 되어있으면 YES, 틀리면 NO를 출력합니다.

 

스택을 이용해 여는 괄호면 스택에 넣고, 닫는 괄호면 스택의 맨 위(top)의 여는 괄호와 쌍이 맞는 지 확인하면 됩니다.

맞다면 top을 pop시키고, 틀리면 바로 false를 리턴합니다. 최종적으로 스택이 비어있으면 true, 남아있는게 있으면 false입니다.

 

코드

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

bool matched(const string& formula) {

	const string opening("({["), closing(")}]");
	stack<char>openStack;

	for (int i = 0; i < formula.size(); i++) {
		if (opening.find(formula[i]) != -1)
			openStack.push(formula[i]);
		else {
			if (openStack.empty())
				return false;
			if (opening.find(openStack.top()) != closing.find(formula[i]))
				return false;
			openStack.pop();
		}
	}

	return openStack.empty();
}


int main()
{
	int C;
	cin >> C;
	while (C--) {
		string formula;
		cin >> formula;
		if (matched(formula))
			cout << "YES" << '\n';
		else
			cout << "NO" << '\n';
	}
}

결과