Stack - C와 Python 비교(2)

스택의 예시로 많이 쓰는 것은 괄호 검사기이다. 프로그래밍을 하다보면 insert가 눌려져서 괄호가 하나씩 없거나 많아서 오류난 경험이 한 번 씩은 있을것이다. 이를 검사하는 프로그래밍을 할 것이다.

일단 C로 한 번 구현해보겠다.

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100

typedef int element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
}StackType;

void init_stack(StackType* s) {
	s->top = -1;
}
int is_empty(StackType* s) {
	return (s->top == -1);
}
int is_full(StackType* s) {
	return (s->top == (MAX_STACK_SIZE - 1));
}
void push(StackType* s, element item)
{
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else s->data[++(s->top)] = item;
}
element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[(s->top)--];
}

int check_matching(const char* in) {
	StackType s;
	char ch, open_ch;
	int i, n = strlen(in);
	init_stack(&s);

	for (i = 0; i < n; i++) {
		ch = in[i];
		switch (ch)
		{
		case'(': case'[': case'{':
			push(&s, ch);
			break;

		case')': case']': case'}':
			if (is_empty(&s)) return 0;
			else {
				open_ch = pop(&s);
				if ((open_ch == '(' && ch != ')') ||
					(open_ch == '[' && ch != ']') ||
					(open_ch == '{' && ch != '}')) {
					return 0;
				}break;

			}
		}
	}if (!is_empty(&s)) return 0;
	return 1;
}
int main(void) {
	char* p = "{A[(i+1)]=0;}";
	if (check_matching(p) == 1)
		printf("%s 괄호 검사 성공\n", p);
	else {
		printf("%s 괄호 검사 실패\n", p);
	}
	return 0;
}

앞서 정의한 스택을 구현하고 int check_matching이라는 함수를 구현하여 검사를 완료하는 코드이다.

C로 구현한 괄호 검사기

C는 블로그의 주 목적 언어가 아니므로 자세한 설명은 생략하겠다.

파이썬으로 구현한 괄호검사기이다.

class Stack:
    def __init__(self):
        self.top=[]
    def isEmpty(self):return len(self.top) == 0
    def size(self): return len(self.top)
    def clear(self): self.top=[]
    def push(self,item): # 삽입
        self.top.append(item)
    def pop(self): # 삭제(마지막 부분)
        if not self.isEmpty():
            return self.top.pop(-1)
    def peek(self): # 맨 위의 항목을 반환
        if not self.isEmpty():
            return self.top[-1]
def checkBrackets(statement):
    stack = Stack()
    for ch in statement:
        if ch in ('(','{','['): # 처음 시작 괄호를 스택에 넣는다.
            stack.push(ch)
        elif ch in (')','}',']'):
            if stack.isEmpty(): # 처음 시작 괄호가 스택에 없는데 닫는게 나와버리면 안됨.
                return False
            else:
                left = stack.pop() # 하나씩 뺀다.
                if (ch == ']' and left != '[') or (ch == '}' and left != '{') or (ch == ')' and left != '('):
                    return False # 닫는 괄호인데 하나씩 뺐을 때 짝이 안맞으면 안됨.
    return stack.isEmpty() # 비어야된다. 남아있으면 False 반환

사실 쥬피터 노트북 상에서는 class Stack을 한 번 정의해 놓고 계속 사용하기 때문에 그 전장에서 정의한 클래스 스택은 다시 적어줄 필요가 없지만 다시 한 번 적었다.

C의 main에서 작성한 코드의 python 버전이다. python 버전은 약간 검사를 추가했다.

ch=("A[(i+1)]=0","if((i==0) &&(j==0)","A[(i+1])=0")
for c in ch:
    m=checkBrackets(c)
    print('{} 검사 결과는 {}'.format(c,m))

python 괄호 검사 결과

3개의 문장을 검사하고 반환값은 T/F로 나타내었다.

 

python 검사기의 자세한 설명이 부족한 것 같아 추가하겠다. chekBrackets의 함수를 통해 문자열을 입력받고 처음에 시작괄호를 먼저 스택에 넣는다. 그리고 닫는 괄호가 나오면 스택 안의 저장된 값을 하나씩 뺀다.

이 때 관점의 변화가 필요하다. 옳은 경우를 알고리즘으로 구현하는 것보다 틀린 경우를 구현하는 것이 더욱 효율적이므로 틀렸을 때의 경우를 생각하여 코드를 작성한다.

elif 안에 if 문 부분에서 스택이 비었는데 닫는 괄호가 나오면 False 값을 리턴한다. 이는 여는 괄호가 나오지도 않았는데 닫는 괄호가 나왔다는 의미이다.

다음으로 elif 안에 else 문에 대해서 살펴보겠다. 소괄호는 소괄호, 중괄호는 중괄호, 대괄호는 대괄호로 짝이 맞아야 한다. 맞지 않을 경우에는 False를 리턴한다. 이 부분에서 앞서 말한 관점의 변화가 필요하다는 것이다. 맞는 경우를 생각하다 보면 코드는 길어지게 되고 수행시간은 더욱 길어질 것이다.

그리고 마지막으로 isEmpty를 반환한다. 모든 짝이 맞아서 괄호검사가 완료되면 스택은 비어져야되기 때문에 True가 되고 남아있다면 False가 반환이 된다.

참고로 숫자나 문자는 생략한 for 문 줄에 else문에서 걸러진다. 즉, 무시하는 것이다.

 

방금 설명한 알고리즘은 위의 C에서도 똑같이 구현이 되었다. 따라서 C 자료구조 검색한 분도 밑에 설명을 읽으시면 이해가 가실 것이다.