6. 데이터 구조 - 스택의 응용(후위 표기 수식의 정의와 계산)

1. 후위표기 수식이란?

우리는 많은 수식을 사용한다. 그중 우선 순위가 다른 연산자들이 있어 계산을 해야하는 순서가 정해져 있다.

우리야 각각의 연산자들의 모양을 보고 우선 순위를 파악하지만, 컴퓨터는 어떠한 방식으로 수식을 계산할까?

 

수식을 표기하는 방식에는 3가지 방식이 있고, 이를 구분하는 방식은 연산자와 피연산자의 위치이다.

1. 중위표기법 : 연산자가 피연산자 사이에 있음
2. 후위표기법 : 연산자가 피연산자 뒤에 있음
3. 전위표기법 : 연산자가 피연산자 앞에 있음

 

<수식표기의 예>

중위	전위	후위
3+4*5	+3*45	345+*
a*b+5	+*ab5	ab*5+

 

컴퓨터는 이 3가지 표기중 후위표기법을 사용한다. 그래서 프로그래머가 인간들이 자주쓰는 표기법인 중위표기법으로 작성하면 컴파일러는 이것을 후위표기법으로 바꾸어 사용한다.

 

그 이유는 계산의 편의성에 있다. 우리가 자주쓰는 중위표기법 같은 경우는 계산 순서가 뒤바뀔수도 있기 때문에 수식을 끝까지 다 파악한 후에 순서에 맞게 계산해야 하지만, 후위표기법은 앞에서 부터 순차적으로 계산이 가능하다. 

 

그렇다면 이제 이 후위표기 수식을 스택을 사용해서 계산해보자.

 

---

2. 스택의 응용 - 후위표기 수식 편

수식을 맨 앞에서 부터 스캔해 피연산자이면 스택에 저장하고, 연산자이면 필요한 수만큼의 피연산자를 스택에서 꺼내 연산을 실행한 후 연산의 결과를 다시 스택에 저장하면 된다.(말로 표현하니 조금 어렵지만 직접 예를 들어서 설명해보자.)

 

ex) 82/3-32*+ 의 계산 과정에서의 스택의 사용

	스택
	[0]	[1]	[2]	[3]	[4]	[5]
8	8
2	8	2
/	4(8/2)
3	4	3
-	1(4-3)
3	1	3
2	1	3	2
*	1	6(3*2)
+	7(1+6)

---

• 숫자를 스택에 푸시(push):
  • 8을 스택에 푸시.
  • 2를 스택에 푸시.
• 연산자 /을 만나면:
  • 스택에서 두 개의 숫자를 꺼냄 (op2 = pop(&s) , op1 = pop(&s))
  • 8 / 2를 계산하고 그 결과를 다시 스택에 푸시.
• 나머지 숫자와 연산자들에 대해 동일한 과정 반복:
  • 스택에 3을 푸시.
  • - 연산자를 만나면, 스택에서 두 개의 숫자를 팝(pop)하여 빼기 연산을 수행하고 결과를 푸시.
  • 3, 2를 스택에 푸시.
  • * 연산자를 만나면, 두 숫자를 팝하여 곱셈을 수행하고 결과를 푸시.
  • 마지막으로 + 연산자를 만나면 두 숫자를 팝하여 덧셈을 수행.

 

---

 

자 이제 그럼 직접 코딩으로 구현을 해보자.

 

3. 후위표기식 계산을 스택으로 구현하기(단 피연산자가 한 문자로 된 숫자라고 가정한다.)

<기본 stack 구현>

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

#define stack_size 100

typedef struct {
	int size[stack_size];
	int top;
}stacktype;


void init_stack(stacktype* s) {
	s->top = -1;//상자의 높이를 확인할 변수 (배열로 구현하기 때문에 맨 아래가 1이 아닌 0이다. 그래서 초기화(아무것도 없는 상태)일때는 -1로 표시한다.)
}


int is_empty(stacktype* s) {
	return(s->top == -1);
}

int is_full(stacktype* s) {
	return(s->top == stack_size - 1); //배열이 0부터 시작하기때문에 (끝 - 1)를 해줘야 꽉 찼음을 나타낸다.
}

void push(stacktype* s,int a) {
	if (is_full(s)) {
		printf("꽉찼습니다");
		return;
	} //만약 상자를 쌓아 올릴 곳이 꽉 찼다면 더이상 상자를 쌓지말고 중지한다.

	s->size[++s->top] = a; //top 즉 상자의 높이를 하나 올려주고 a라는 상자를 추가한다.
}

int pop(stacktype* s) {
	if (is_empty(s)) {
		printf("비어있습니다");
		return 0;
	}//만약 상자를 쌓아 올릴 곳이 비어있다면 더이상 상자를 빼지말고 중지한다.

	int result = s->size[s->top--]; //top높이에 있는 상자를 빼고 top높이를 하나 줄인다.

	return result;
}

int peek(stacktype* s) {
	if (is_empty(s)) {
		printf("비어있습니다");
		return 0;
	}

	int result = s->size[s->top]; //top높이의 있는 상자가 무엇인지 확인한다.(빼지는 않음))

	return result;
}

//---------------------------------------------
//여기까지가 기본 스택 구현

여기까지는 기본 stack 구현이다. 만약 이해가 되지 않는다면

https://spatz.tistory.com/119

이 링크를 참조하면 도움이 될 것이다..

 

<eval 함수 구현>

int eval(char exp[]) {

	int op1, op2, value = 0; 
	int len = strlen(exp); // 입력받은 수식의 길이를 알기 위해 <string.h> 해더 파일에서 가져옴
	char ch;
	stacktype s;

	init_stack(&s);

	for (int i = 0; i < len; i++) {
		ch = exp[i]; // 받은 수식을 ch라는 문자에 저장

		if (ch != '+' && ch != '-' && ch != '*' && ch != '/') { // 만약 ch로 들어온 문자가 피연산자라면?
			value = ch - '0'; // 문자열을 실제 숫자로 변환하기 위해 사용함
			push(&s, value); // 그 피연산자를 스택에 저장
		}
		else { // 만약 ch로 들어온 문자가 연산자라면?
			op2 = pop(&s); 
			op1 = pop(&s); //두개의 피연산자를 꺼냄
			switch (ch) //swith문을 통해 각 케이스 마다 계산 후 스택에 저장
			{
			case '+': push(&s,op1 + op2); break;
			case '-': push(&s,op1 - op2); break;
			case '*': push(&s,op1 * op2); break;
			case '/': push(&s,op1 / op2); break;
			

			}
		}
	}

	return pop(&s);
	
}

가장 중요한 부분은 들어온 수식을 하나하나 쪼개서 그것이 연산자인지 피연산자인지를 파악하고 이를 구별해 계산하는 것이다. 코드를 한줄 한줄 천천히 생각해보면 이해하기 편할 것이다.

 

<최종 코드>

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

#define stack_size 100

typedef struct {
	int size[stack_size];
	int top;
}stacktype;


void init_stack(stacktype* s) {
	s->top = -1;//상자의 높이를 확인할 변수 (배열로 구현하기 때문에 맨 아래가 1이 아닌 0이다. 그래서 초기화(아무것도 없는 상태)일때는 -1로 표시한다.)
}


int is_empty(stacktype* s) {
	return(s->top == -1);
}

int is_full(stacktype* s) {
	return(s->top == stack_size - 1); //배열이 0부터 시작하기때문에 (끝 - 1)를 해줘야 꽉 찼음을 나타낸다.
}

void push(stacktype* s,int a) {
	if (is_full(s)) {
		printf("꽉찼습니다");
		return;
	} //만약 상자를 쌓아 올릴 곳이 꽉 찼다면 더이상 상자를 쌓지말고 중지한다.

	s->size[++s->top] = a; //top 즉 상자의 높이를 하나 올려주고 a라는 상자를 추가한다.
}

int pop(stacktype* s) {
	if (is_empty(s)) {
		printf("비어있습니다");
		return 0;
	}//만약 상자를 쌓아 올릴 곳이 비어있다면 더이상 상자를 빼지말고 중지한다.

	int result = s->size[s->top--]; //top높이에 있는 상자를 빼고 top높이를 하나 줄인다.

	return result;
}

int peek(stacktype* s) {
	if (is_empty(s)) {
		printf("비어있습니다");
		return 0;
	}

	int result = s->size[s->top]; //top높이의 있는 상자가 무엇인지 확인한다.(빼지는 않음))

	return result;
}

//---------------------------------------------
//여기까지가 기본 스택 구현

int eval(char exp[]) {

	int op1, op2, value = 0; 
	int len = strlen(exp); // 입력받은 수식의 길이를 알기 위해 <string.h> 해더 파일에서 가져옴
	char ch;
	stacktype s;

	init_stack(&s);

	for (int i = 0; i < len; i++) {
		ch = exp[i]; // 받은 수식을 ch라는 문자에 저장

		if (ch != '+' && ch != '-' && ch != '*' && ch != '/') { // 만약 ch로 들어온 문자가 피연산자라면?
			value = ch - '0'; // 문자열을 실제 숫자로 변환하기 위해 사용함
			push(&s, value); // 그 피연산자를 스택에 저장
		}
		else { // 만약 ch로 들어온 문자가 연산자라면?
			op2 = pop(&s); 
			op1 = pop(&s); //두개의 피연산자를 꺼냄
			switch (ch) //swith문을 통해 각 케이스 마다 계산 후 스택에 저장
			{
			case '+': push(&s,op1 + op2); break;
			case '-': push(&s,op1 - op2); break;
			case '*': push(&s,op1 * op2); break;
			case '/': push(&s,op1 / op2); break;
			

			}
		}
	}

	return pop(&s);
	
}

int main(void) {
	int result;
	printf("후위표기식은 82/3-32*+\n");
	result = eval("82/3-32*+");
	printf("결과값은 %d\n", result);
}