문제 요약

문제 링크 : https://www.acmicpc.net/problem/4949

어떤 문자열이 입력으로 주어졌을 때, 괄호가 균형이 맞는지 판단하여 맞으면 yes, 아니면 no를 출력하는 프로그램을 작성해야 함. 프로그램은 "." 하나를 찍으면 종료된다. 균형이 맞는지에 대한 조건은 아래와 같다.

• () 닫는 소괄호와 여는 소괄호가 짝을 이룬다.
• [] 닫는 대괄호와 여는 대괄호가 짝을 이룬다.
• ( [] ) , [ ( ( ) ) ] , [ [ [ ( [ ] ) ] ] ] 모두 균형이 맞는 괄호의 예시이다.
• ( ], [ ( ] ], ( ( ( ) ] ) 는 균형이 맞지 않는 괄호이다.

풀이 과정

1. 입력이 "." 이면 프로그램을 종료한다.
2. 그렇지 않으면, 입력된 문자열을 하나씩 탐색하면서 괄호인지 살펴본다.
3. 여는 괄호 ( '(' 또는 '[' ) 가 나오면 스택에 넣어둔다.
4. 닫는 괄호 ( ')' 또는 ']' ) 가 나오면, 가장 최근에 스택에 쌓아둔 괄호와 비교하여 짝인지 살펴본다.
5. 짝이면 stack에 있던 괄호를 pop하고, 짝이 아니라면 문자열을 하나씩 탐색하는 과정을 종료한다.
6. 스택에 남아있는 괄호가 없다면 괄호가 모두 짝이 있기 때문에 yes를 출력하고, 그렇지 않으면 균형이 없기 때문에 no를 출력한다.
   
   

코드

C (스택 직접 구현)

#include <stdio.h>
//#include <stdlib.h>
//#include <stack>
//#include <string.h>

//using namespace std;

int main(void)
{
	char sentence[101];
	char stack[101];
	int pos = 0;
	
	while (1)
	{
		gets(sentence);
		if (sentence[0] == '.') break;
		for (int i = 0; sentence[i] != '.'; i++)
		{
			if (sentence[i] == ')')
			{
				if ( pos > 0 && stack[pos-1] == '(') pos--;
				else stack[pos++] = sentence[i];

			}
			else if (sentence[i] == ']')
			{
				if (pos > 0 && stack[pos - 1] == '[') pos--;
				else stack[pos++] = sentence[i];
			}
			else if (sentence[i] == '(') stack[pos++] = sentence[i];
			else if (sentence[i] == '[') stack[pos++] = sentence[i];
		}
		if (pos <= 0) printf("yes\n");
		else printf("no\n");
		pos = 0;
	}
}

C++ (STL stack 사용)

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main(void)
{
	stack<char> s; //스택 생성
	string sentence; //문자 저장 변수 선언
	bool flag = 0;
	while (1)
	{
		getline(cin, sentence); //띄어쓰기가 있는 문자를 입력받음
		if (sentence == ".") break;
		for (int i = 0; sentence[i] != '.'; i++)
		{
			if (sentence[i] == '(' || sentence[i] == '[') s.push(sentence[i]); //여는 괄호이면 스택에 push
			else if (sentence[i] == ')') // 닫는 괄호이면
			{
				if (!s.empty() and s.top() == '(') s.pop(); //짝을 만났으면 pop
				else
				{
					flag = 1; 
					break;
				} //짝을 못 만났으면 더 이상 탐색할 필요가 없으니 flag = 1로 변경 후 실행 종료
			}
			else if (sentence[i] == ']')
			{
				if (!s.empty() and s.top() == '[') s.pop(); //짝을 만났으면 pop
				else
				{
					flag = 1;
					break;
				} // 짝을 못 만났으면 더 이상 탐색할 필요가 없으니 flag = 1변경 후 실행 종료
			}
		}
		if (s.size() == 0 && flag == 0) cout << "yes\n";
		else cout << "no\n"; //스택에 괄호가 남아있거나 flag가 1이라면 no 출력

		while (!s.empty())
		{
			s.pop(); // 스택 초기화
		}
		flag = 0; //flag 초기화
	}

}

Python

import sys
stack = []
while True:
    sentence = sys.stdin.readline().rstrip()
    flag = True
    if sentence == '.':
        break
    for i in sentence:
        if i == '(' or i == '[':
            stack.append(i)
        elif i == ']':
            if stack and stack[-1] == '[':
                stack.pop()
            else:
                flag = False
                break
        elif i == ')':
            if stack and stack[-1] == '(':
                stack.pop()
            else:
                flag = False
                break
    if not stack and flag:
        print("yes")
    else:
        print("no")
    stack = []
    flag = True