백준 4949 균형잡힌 세상

 

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

 

서론

STL의 스택을 이용하면 쉬운 문제.

연결리스트로 스택을 구현해봤다.

 

아이디어

문자열 한줄을 입력받고

첫 문자부터 마침표까지 탐색하는데,

문자는 무시한다.

왼쪽 괄호는 스택에 넣는다.

오른쪽 괄호는 스택의 top이 짝이 맞는 왼쪽 괄호라면 스택을 pop한다.

마침표까지 탐색하고 스택이 비어있다면 옳은 문자열이다.

 

구현

반복문에서 매번 메모리해제 해주지 않으면 메모리초과 발생.

//c++

#include <iostream>
#include <cstdlib>

using namespace std;

char inputString[101];

typedef struct node {
	char item;
	node* next;
}node;

typedef struct stack {
	node *top;
}stack;

void init(stack *s) {
	node *head = (node*)malloc(sizeof(node));
	s->top = head;
	head->item = NULL;
	head->next = NULL;
}

void push(stack* s, char input) {
	node *now = (node*)malloc(sizeof(node));
	now->item = input;
	now->next = s->top;
	s->top = now;
}

void pop(stack* s) {
	node *now;
	now = s->top;
	s->top = now->next;
	free(now);
}

bool empty(stack *s) {
	if (s->top->item == NULL) return true;
	else return false;
}

void mfree(stack *s) {
	while (s->top != NULL) {
		node *now;
		now = s->top;
		s->top = now->next;
		free(now);
	 }
}

int main() {
	while (1) {
		cin.getline(inputString, 101);
		if (inputString[0] == '.') break;
		stack s;
		init(&s);
		for (int i = 0; i < 101; i++) {
			char cur = inputString[i];
			if (cur == '(' || cur == '[') push(&s, cur);
			else if (cur == ')' || cur == ']') {
				if (s.top->item == '(' && cur == ')') {
					pop(&s);
				}
				else if (s.top->item == '[' && cur == ']') {
					pop(&s);
				} else push(&s, cur);
			}
			else if (cur == '.') {
				if (empty(&s) == true) {
					cout << "yes" << endl;
					break;
				}
				else {
					cout << "no" << endl;
					break;
				}
			}
			else continue;
		}
		mfree(&s);
	}
}