[C언어] Stack 구현 문제 풀이

지금은 정글 4주차 C언어로 자료구조 문제를 풀고 있는 중이다.
문제를 풀다가 어려웠던 내용을 블로그로 포스팅을 하려고 한다.

 

 

문제 

DATA-STRUCTURES(Q7_C_SQ)

(balanced) Write a C function balanced() that determines if an expression comprised of
the characters ()[]{} is balanced. The prototype for the balanced() function is given
below:
The function prot
otype is given as follows:
int balanced(char *expression);

For example, the following expressions are balanced because the order and quantity of the
parentheses match:
()
([])
{[]()[]}

 

위와 같이 ()([]) {[]()[]} 처럼 짝이 괄호가 짝이 맞는지 안맞는지 확인해서 결과를 출력하는 문제이다.

 

 

int balanced(char *expression){
/* add your code here */
}

위와같은 코드를 작성하면된다.

 

먼저 함수를 보면 알겠지만 문자열로 인자가 주어지게 된다.

이는 포인터 변수이니 우리는 문자열의 주소값을 하나씩 증가하면서 비교를 하는 방법을 선택 할 것이다.

 

처음에 들어간 괄호는 맨 마지막에 닫히게 된다. 예를들어 (로 시작한 괄호 안에 {}가 있을 수 있고 []가 있을 수 있고 또는 ( 가 또 있을 수 있게 된다.

결론적으로는 처음에 시작한 괄호는 닫는 괄호가 나올때까지 안에 어떤 괄호들도 들어갈 수 있다. 방식을 생각했을때 스택을 통해 문제를 풀어야 겠다라는걸 생각할 수 있었다.

 

이처럼 스택에서 같은 모양의 닫는 괄호가 들어오려고 할때 이를 미리 비교해서 stack에서 pop을 하면 한 쌍이 맞춰진다고 확인할 수 있게 된다.

 

만약 문자열이 다 끝났는데 스택이 비워져 있지 않다면 문자열은 쌍이 안맞는 괄호를 가지고 있는것으로 판별할 수 있게 된다.

 

이제 이 로직에 맞게 코드를 작성해보자.

 

코드구현

1. stack 변수 초기화

	Stack s;
	s.ll.head=NULL;
	s.ll.size=0;

 

스택변수를 선언 하고 이를 초기화 한다.

 

2. 문자열의 값을 찍을 변수 및 stack의 top의 값을 저장할 변수 선언

	char e = *expression;
	char tmp;

 

3. 반복문 설정

while(e!='\0')

문자열이 끝날때까지 코드를 반복한다 '\0'은 NULL을 의미한다.

 

3-1. 반복문 설정

	while(e!='\0'){
		if(e=='{'||e=='('||e=='['){
			push(&s,e);
		}
		if(e=='}'||e==')'||e==']'){
			if (isEmptyStack(&s))
				return 1;
			tmp = pop(&s);
			if(tmp=='{'&&e!='}') return 1;
			if(tmp=='['&&e!=']') return 1;
			if(tmp=='('&&e!=')') return 1;
		}
		expression += 1;
		e = *expression;	
	}

우리는 여는 괄호가 들어올때 스택에 넣어야 함으로 조건문을 걸어야 한다.

닫는괄호가 들어올때 스택이 비워져 있는 경우를 예외처리를 미리 해줘야한다.

닫는괄호가 들어오면 스택의 top에 있는 괄호를 꺼내서(pop) 비교하고 만약 조건에 맞는 괄호가 없으면 바로 쌍이 안맞는걸로 판별한다.

만약 맞다면 문자열 주소를 증가시켜서 while문을 반복하도록 한다.

다 while문을 이상 없이 종료했다면 이는 쌍이 맞는 괄호 문자열이라고 할 수 있다.

 

마치며

C언어로 자료구조를 구현하면서 포인터와 메모리할당에 대해서 더 공부를 할 수 있게 되는것 같다.

처음에는 코드를 좀 간결하고 간지나게 작성하고 싶어서 아스키 코드로 비교하는걸 만드려고 했다가 많은 시간을 소비하게 되었다.

일단 코드를 완성시키는데 목적을 두긴 해야할 것 같긴하다. 어찌 됬던 안돌아가는 코드보다 돌아가는 코드가 100배 낫다.