[백준 4949] 균형잡힌 세상

문제
어떠한 문장이 있을 때 괄호들이 균형이 잡혀있는지 검사한다.
소괄호는 소괄호끼리 대괄호는 대괄호끼리 짝을 이뤄야한다.
균형잡힌 문자열이라면 yes를 아니라면 no를 출력한다.

입력
여러 줄에 걸쳐서 문자열이 입력될 때 각 문자열이 균형이 잡혔는지 검사한다.
만약 "."이 들어온다면 문자 입력을 종료한다.

출력
각 문자열에 yes 또는 no를 출력한다.

---

접근

괄호에 대해 관심을 가져야한다. 균형이 잡혔다면 현재의 닫는괄호가 가장 최근에 나온 여는괄호와 짝이 맞아야한다.

스택은 가장 마지막에 넣은 데이터가 가장 위에 쌓이기 때문에 괄호를 스택에 넣어보도록 한다.

 

구현

기본적으로 while문안에서 실행이 된다.

괄호를 넣을 스택을 생성하고 string형의 input에 getline으로 문자열을 입력받는다.

만약 입력받은 문자열이 "."이라면 while문을 종료시키도록 한다.

string input;
stack<char> st;
getline(cin, input);
if (input==".")
	break;

 

입력받은 문자열을 탐색한다.

여는 괄호가 나온다면 스택에 넣는다.

그리고 이때 스택이 비었을 때와 비어있지 않을 때를 나눠서 검사를 하는데 아래의 코드는 스택이 비어있을 때이다.

스택이 비어있는데 닫는 괄호가 나왔다면 스택에 넣고 for문을 종료시킨다.

닫는 괄호를 스택에 넣는 이유는 문자열을 모두 검사했을 때 스택이 비어있지 않는다면 균형잡힌 것이 아닌걸로 판단하기 위함이다.

		for (int i = 0; i < input.size(); i++) {
			if (input[i] == '(' || input[i] == '[')
				st.push(input[i]);
			if (st.empty()) {
				if (input[i] == ')' || input[i] == ']') {
					st.push(input[i]);
					break;
				}
			}

 

그 다음 스택이 비어있지 않았을 때

닫는 괄호가 나왔다면 스택의 TOP이 해당 괄호와 맞는 여는 괄호라면 POP을 진행한다. 하지만 짝이 맞지않는 여는 괄호라면 스택에 닫는 괄호를 넣고 break를 한다. 

			else {
				if (input[i] == ')')
				{
					if (st.top() == '(')
						st.pop();
					else
					{
						st.push(input[i]);
						break;
					}
				}
				else if (input[i] == ']') {
					if (st.top() == '[')
						st.pop();
					else {
						st.push(input[i]);
						break;
					}
				}
			}

		}

 

입력받은 문자열을 모두 탐색했을 때

스택이 비어있으면 yes를 비어있지 않다면 no를 출력한다.

		if (st.empty())
			cout << "yes" << endl;
		else
			cout << "no" << endl;

---

전체 코드

#include <iostream>
#include<algorithm>
#include <vector>
#include<cstring>
#include<stack>
#include<string>

using namespace std;



int main()
{	
	string input;
	
	while (1) {
		stack<char> st;
		getline(cin, input);
		if (input==".")
			break;
		for (int i = 0; i < input.size(); i++) {
			if (input[i] == '(' || input[i] == '[')
				st.push(input[i]);
			if (st.empty()) {
				if (input[i] == ')' || input[i] == ']') {
					st.push(input[i]);
					break;
				}
			}
			else {
				if (input[i] == ')')
				{
					if (st.top() == '(')
						st.pop();
					else
					{
						st.push(input[i]);
						break;
					}
				}
				else if (input[i] == ']') {
					if (st.top() == '[')
						st.pop();
					else {
						st.push(input[i]);
						break;
					}
				}
			}

		}
		if (st.empty())
			cout << "yes" << endl;
		else
			cout << "no" << endl;
	}
	return 0;
}