[Algospot] Mismatched Brackets (문제 ID : BRACKETS2)

문제

Best White is a mathematics graduate student at T1 University. Recently, he finished writing a paper and he decided to polish it. As he started to read it from the beginning, he realized that some of the formulas have problems: some of the brackets are mismatched! Since there are so many formulas in his paper, he decided to check their validity with a computer program.

The following kinds of brackets are included in Best White’s paper.

• Round brackets are opened by a ( and closed by a ).

• Curly brackets are opened by a { and closed by a }.

• Square brackets are opened by a [ and closed by a ].

A formula is said well-matched when the following conditions are met:

1. Every bracket has a corresponding pair. ( corresponds to ), [ corresponds to ], et cetera.

2. Every bracket pair is opened first, and closed later.

3. No two pairs "*cross*" each other. For example, [(]) is not well-matched.

Write a program to help Best White by checking if each of his formulas is well-matched. To make the problem easier, everything other than brackets are removed from the formulas.

 

입력

The first line of the input will contain the number of test cases C (1≤C≤100). Each test is given in a single line as a character string. The strings will only include characters in "[](){}" (quotes for clarity). The length of the string will not exceed 10,000.

 

출력

For each test case, print a single line "YES" when the formula is well-matched; print "NO" otherwise. (quotes for clarity)

---

괄호가 짝이 맞는지를 검사하는 문제이다.

이런류의 문제는 꽤 많이 풀어봤기 때문에 스택을 이용해 어렵지 않게 풀었다.

여는 괄호 (, {, [가 나오면 스택에 각각 1, 2, 3을 넣어주고 닫는 괄호가 나올때 스택의 탑이 각자의 여는 괄호와 맞는지를 체크해주면 된다. 즉 )가 나오면 st.top()==1인지를 봐줘야된다. 주의할 점은 닫는 괄호가 나올 땐 스택이 비어있어선 안된다는것이다. 비어있으면 top()연산을 실행할 때 세그멘테이션 오류가 뜨기 때문에 조건을 미리 잡아주자.

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/BRACKETS2.cpp

chosh95/STUDY

C++ 코드 

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

int C;
string match(string str) {
	stack<int> st;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') st.push(1);
		else if (str[i] == '{') st.push(2);
		else if (str[i] == '[') st.push(3);
		else if (str[i] == ')') {
			if (st.empty()) return "NO";
			if (st.top() == 1) st.pop();
		}
		else if (str[i] == '}') {
			if (st.empty()) return "NO";
			if (st.top() == 2) st.pop();
		}
		else if (str[i] == ']') {
			if (st.empty()) return "NO";
			if (st.top() == 3) st.pop();
		}
	}
	if (st.empty())
		return "YES";
	else
		return "NO";
}

int main()
{
	cin >> C;
	while (C--) {
		string str;
		cin >> str;
		cout<<match(str)<<endl;
	}
}