[C programming] 스택(Stack)

C programming -스택(Stack)

 

 

리눅스 환경에서 네트워크 프로그래밍을 공부하기 위해서 C언어를 다시 복습해야 할 필요성을 느꼈습니다. 따라서 이번 기회에 배열부터 전처리기까지 내용들을 정리하겠습니다.

 

---

스택이란?

출처 : https://www.programiz.com/dsa/stack

 

스택은 선형 자료구조로서 Last In First OUT (LIFO) 규칙을 따릅니다. 즉, 마지막에 들어온 요소가 가장 먼저 제거된다는 뜻입니다. 마치 접시들이 쌓여있는 모습이라고 생각하면 됩니다.

 

#define MAX 10
int stack[MAX];
int top;

int push(int t) {
	if (top >= MAX-1) {
		printf(“Stack overflow\n”);
		return -1;
	}
	stack[++top] = t;
	return t;
}

int pop() {
	if (top < 0) {
		printf(“Stack underflow\n”);
		return -1;
	}
	return stack[top--];
}

 

 

스택의 기본적인 구현은 위와 같이 이루어집니다. 배열과 배열의 최상위 위치를 알리는 top이라는 변수를 선언합니다. top을 통해서 스택이 얼마나 차있는지 확인하여 push()와 pop()을 수행합니다.

 

push()는 요소를 추가하는 작업으로서 top의 값을 증가시키고 스택의 최상위 부분에 값을 추가합니다. pop() 은 요소를 제거하는 작업으로 스택의 최상위 부분의 값을 제거하고 top의 값을 감소시킵니다.

 

위와 같은 내용을 바탕으로 스택을 활용하는 방법을 살펴보겠습니다.

 

---

 

스택 응용 - 수식의 후위 표기법

• 중위 표기법
  • A * ( ( B + C ) / ( D - E ) )
  •  반드시 괄호가 필요하다
• 후위 표기법
  • ABC+DE-/*

스택을 응용하여 프로그래머가 입력한 중위 표기법을 후위 표기법으로 변활 할 수 있습니다. 변환은 아래와 같은 순서로 이루어집니다.

 

1. '(' 문자는 무시한다.
2. 피연산자는 그대로 출력한다.
3. 연산자는 스택에 푸시한다.
4. ')'를 만나면 스택에서 팝 하여 출력한다.

 

(A + ( B * C ) )의 변환 결과

	출력	스택
A	A
+	A	+
B	AB	+
*	AB	+*
C	ABC	+*
)	ABC*	+
)	ABC*+

 

void postfix(char *post, char *in) {
	char c;
	while(*in) {
		if( *in == ‘)’ ) { // ‘)’를 만나면 푸쉬된 연산자 팝
			*post++ = pop();
			*post++ = ‘ ‘; // 문자의 구분을 위해
			in++;
		} else if( *in == ‘+’ || *in == ‘-’ || *in == ‘*’ || *in == ‘/’ ) {
			push( *in ); // 연산자는 스택에 푸쉬
			in++;
		} else if( *in >= ‘0’ && *in <= ‘9’ ) { // 피연산자 출력
			do {
				*post++ = *in++;
			} while(*in >= ‘0’ && *in <= ‘9’ );
		} else {
			in++;
		}
	}
	*post = ‘\0’;
}

 

*post는 출력될 값들을 저장하는 String을 가리키는 포인터를 의미하고 *in는 중위 표기법으로 입력된 String을 가리키는 포인터를 의미합니다.

 

---

 

 

여기에 연산자의 우선순위를 고려하는 방법을 추가하여 코드를 수정할 수 있습니다.

 

1. '('를 만나면 스택에 푸시
2. ')'를 만나면 스택에서 '('가 나올 때까지 팝 하여 출력하고 '('는 버림
3. 연산자를 만나면 스택에서 그 연산자보다 낮은 우선순위의 연산자를 만날 때까지 팝 하여 출력한 뒤 자신을 푸시
4. 피연산자는 그대로 출력
5. 모든 입력이 끝나면 스택에 있는 모든 연산자들을 모두 팝 하여 출력

 

( 2 * ( 3 + 8 / 2 ) + 2 ) / 4

	출력	스택
(		(
2	2	(
*	2	(*
(	2	(*(
3	23	(*(
+	23	(*(+
8	238	(*(+
/	238	(*(+/
2	2382	(*(+/
)	2382/+	(*
+	2382/+*	(+
2	2382/+*2	(+
)	2382/+*2+
/	2382/+*2+	/
4	2382/+*2+4	/
	2382/+*2+4/

 

아래와 같은 네 개의 함수를 사용하여 구현합니다.

int get_stack_top() {
    if (top < 0) return -1;
    else return stack[top];
}

 

스택의 가장 높은 부분의 값을 리턴합니다.

 

int is_operator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

 

연산자가 입력되었는지 확인합니다.

 

int precedence( char c ) {
	if ( c == ‘(‘ ) return 0;
	if ( c == ‘+’ || c == ‘-’ ) return 1;
	if ( c == ‘*’ || c == ‘/’ ) return 2;
	else return 3;
}

 

해당 문자의 우선순위를 리턴합니다. '('는 가장 낮은 0이며 '+'와 '-'는 1 그리고 '*'와 '/'는 2입니다.

 

int is_stack_empty() {
	if (top < 0 ) return 1;
	else return 0;
}

 

스택이 비어있는지 확인하는 함수입니다.

 

실제로 구현된 후위 연산자 변환은 아래와 같습니다.

void postfix(char *post, char *in) {
	char c;
	while( *in ) {
		if ( *in == ‘(‘ ) { // 스택에 push
		push(*in);
		in++
	} else if ( *in == ‘)’ ) { // )를 만나면 (가 나올때까지 pop
		while( get_stack_top() != ‘(‘ ) {
			*post++ = pop();
			*post++ = ‘ ‘;
		}
		pop();
		in++;
	} else if( is_operator( *in ) ) { // 연산자일 때
		while( !is_stack_empty() &&
			precedence(get_stack_top()) >= precedence( *in ) ) {
			*post++ = pop();
			*post++ = ‘ ‘;
		}
		push(*in); // 자신은 push
		in++;
	} else if( *in >= ‘0’ && *in >= ‘9’ ) { // 피연산자는 출력
		do {
			*post++ = *in++;
		} while(*in >= ‘0’ && *in >= ‘9’ );
			*post++ = ‘ ‘;
		} else in++;
	}
	while( !is_stack_empty() ) {// 스택에 있는 내용 모두 pop
		*post++ = pop();
		*post++ = ‘ ‘;
	}
	*post = ‘\0’;
}

 

---

 

마지막으로 후위 표기법 상태인 식을 연산하는 방법을 살펴보겠습니다.

1. 숫자를 만나면 스택에 푸시
2. 연산자를 만나면 스택에서 팝을 두 번, 그 데이터를 가지고 연산한 다음 그 결과를 스택에 다시 푸시

 

2 3 * 6 2 / + 4 -

	스택	설명
2	2	push
3	2 3	push
*	*	pop 2번, 2 * 3 = 6
6	6 6	push
2	6 6 2	push
/	6 3	pop 2번, 6 / 2 = 3
+	9	pop 2번, 6 + 3 = 9
4	9 4	push
-	9 - 4	pop 2번, 9 - 4 = 5

 

실제로 구현된 코드는 아래와 같습니다.

int cal(char *p) {
	int i;
	while(*p) {
		if( *p >= ‘0’ && *p <= ‘9’) {
		i = 0;
			do {
				i = i * 10 + *p – ‘0’;
				p++;
			} while(*p >= ‘0’ && *p <= ‘9’ );
			push(i);
		} else if (*p == ‘+’) {
			push( pop() + pop() );
			p++;
		} else if(*p == ‘*’) {
			push( pop() * pop() );
			p++;
		} else if(*p == ‘-’) { // 교환 법칙 성립하지 않는 연산자
			i = pop();
			push( pop() – i );
			p++;
		} else if(*p == ‘/’) {// 교환 법칙 성립하지 않는 연산자
			i = pop();
			push ( pop() / i );
			p++;
		} else {
			p++;
		}
	}
	return pop();
}

 

---