[알고리즘] 문제풀이 연습

[알골90제] 54번 - 올바른 괄호 : STACK 이용

ddgoori 2019. 7. 30. 16:50

*문제 

 

괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다. (())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.


▣ 입력설명 첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다. 
▣ 출력설명 첫 번째 줄에 YES, NO를 출력한다.

 

 

* 풀이

 

1) 여는 괄호면 push

2) 닫는 괄호면 pop

3) 여는 괄호면 push

.

.

.

 

4) 올바른 괄호라면 string을 다 처리하면 stack이 정확하게 비어있다.

- 고려해야할 상황 (()))( : push push pop pop pop => stack에 가보려하니 없더라.

 

*주의

 

(()))( 의 경우를 위해 => flag만듬

YES YES

NO NO 로 2번 출력하는 것 방지하기 위해 flag를 만들어서 정교하게 조건문 걸어줌

 

* 코드 구현

 

// 54번 - 올바른 괄호(stack) STL 사용

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;

int main() {

	char temp, count = 0;
	int flag = 1; //신호변수 (()))()
	stack<char> s;

	char a[50];
	scanf("%s", &a);

	for (int i = 0; a[i] != '\0'; i++) {
		if (a[i] == '(') s.push(a[i]);
		else {
			if (s.empty()) {
				printf("NO\n");
				flag = 0;
				break;
			}
			else {
				s.pop();
			}
		}
	}
	if (s.empty() && flag == 1) printf("YES\n");
	else if(!s.empty() && flag == 1)printf("NO\n");

	return 0;
}