스택

스택(Stack)이란?

어떠한 자료를 쌓아서 만든 자료구조로 LIFO(Last in First Out)이다.
즉, 가장 마지막에 들어간 데이터가 먼저 접근하는 자료구조이다.
인터넷 창에서 뒤로가기 버튼을 누르면 가장 최근의 페이지로 돌아가는 것, 재귀의 구현 등을 예로 들 수 있다.

스택의 method

스택의 주요 메쏘드로는 push와 pop이 있다.
push는 원소를 삽입하는 메쏘드이고 pop은 가장 최근의 원소를 삭제하여 반환하는 메쏘드이다.

그 외의 보조 method 들도 소개하겠다.

init() : 스택 초기화
top() : 가장 최근에 삽입된 원소 반환(삭제 x)
size() : 저장된 원소의 수 반환
isEmpty() : 원소가 아무 것도 저장되어 있지 않고 비어있는지 여부 반환

스택 method 코드 구현

먼저 stack의 구조체 형태부터 알아보자

스택 구조체

typedef struct Stack {
	char arr[1000];
    int size;
	int top;	
}Stack;

stack 구조체 안에 데이터를 담을 arr배열,
원소의 max 개수를 저장할 size, 마지막 데이터의 위치를 나타낼 top이 있다.

스택 initialize

void stack_init(Stack* stack, int N) {	
	stack->top = -1;
	stack->size = N;
}

스택이 비어있을 때 top의 위치를 -1로 초기화 하고 stack의 max 개수 N을 받아 size에 저장한다.

스택 push

void push(Stack* s, char data) {
	if (s->size - 1 <= s->top) {
		printf("Stack FULL\n");
		return;
	}
	(s->top)++;
	s->arr[s->top] = data;
}

데이터를 받아 스택에 저장하는 메쏘드이다.
이 때 push 하기 전에 유효성 체크를 먼저 해준다.
만약 스택이 꽉 찬 경우, size - 1(스택의 저장 용량)과 top(현재 저장 개수)가 같은 경우 저장을 하지 않고 종료한다.
만약 공간이 남아 있다면 top을 1 증가 시키고 arr[top]에 data를 저장한다.

스택 pop

char pop(Stack* s) {
	if (s->top == -1) {
		return 0;
	}
	int temp = s->arr[s->top];
	s->top--;
	return temp;
}

데이터를 삭제하는 메쏘드이다.
이 때도 push와 마찬가지로 삭제하기 전에 유효성 체크를 해준다.
스택이 비어 있는 경우(top == -1) 바로 종료해주고 비어 있지 않다면 temp에 삭제할 데이터를 먼저 저장하여 준다.
그리고 top을 1 감소시킨뒤 삭제한 데이터를 반환하여 준다.
이 때 배열에 저장한 데이터는 그대로 남아 있지만 top을 1 감소시킴으로써 접근하지 못하도록 하는 것이다.

스택 top

void top(Stack s) {
	if (s.top == -1) {
		printf("Stack Empty\n");
		return;
	}
	printf("%c\n", s.arr[s.top]);
}

top은 가장 위에 저장된 원소를 반환한다.
만약 스택이 비어있다면 바로 종료한다.

스택 empty

int is_empty(Stack* s) { 
	return s->top == -1 ? 1 : 0;
}

top이 -1이라면 스택이 비어있는 것이므로 1을 반환하고 스택이 비어있지 않으면 0을 반환한다.

스택을 응용한 계산기

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#pragma warning(disable:4996)

typedef struct Stack_char { // char형 stack(후위수식을 위한 stack)
	char arr[201];
	int top;
	int size;
}Stack_char;

typedef struct Stack_int { // int형 stack(후위수식 -> 계산을 위한 stack)
	int arr[201];
	int top;
	int size;
}Stack_int;

void stack_int_init(Stack_int* s);
void stack_char_init(Stack_char* s);
char top(Stack_char* s);
void push(Stack_char* s, char data);
void push_int(Stack_int* s, int data);
char pop(Stack_char* s);
int pop_int(Stack_int* s);
int is_empty(Stack_char* s);
int compare(char oper);
int is_operand(char ch);
int do_operator(char op, int x, int y);
void convert_postfix(Stack_char* s, char* infix, char* postfix);
void cal(Stack_char* s, char* infix);
void calculate(char* postfix);

int main() {

	Stack_char stack;
	int N;
	scanf("%d", &N);
	getchar();

	while (N--) {
		stack_char_init(&stack);
		char infix[201];
		gets(infix);  //중위 수식 입력받기

		cal(&stack, infix); //중위수식 계산
	}

	return 0;
}

void cal(Stack_char* s, char* infix) { // cal함수는 두 부분으로 나뉜다

	char postfix[201] = { 0 };

	convert_postfix(s, infix, postfix); // 중위수식을 후위수식으로 바꾸는 함수
	calculate(postfix);	//후위수식을 연산하는 함수
}

void convert_postfix(Stack_char* s, char* infix, char* postfix) { // 후위수식으로 변환, char형 스택 s와 수식 infix, 후위수식을 담을 postfix배열

	int postfix_idx = 0;

	for (int i = 0; infix[i] != '\0'; i++) { //수식 읽기
		char ch = infix[i];

		if (is_operand(ch)) { // ch가 피연산자라면
			postfix[postfix_idx++] = ch; // 후위수식 배열에 넣어라
			if (infix[i + 1] != '\0' && (infix[i + 1] >= '0' && infix[i + 1] <= '9')) { // 2자리 수 이상일 경우(숫자 다음이 또 숫자)
				ch = '~';	// 숫자와 숫자사이에 ~표시를 넣어 이어져 있음을 임의로 표시해준다
				while (top(s) != '(' && !is_empty(s) && (compare(ch) <= compare(top(s)))) // 이 ~ 연산자는 우선순위가 가장 높다
					postfix[postfix_idx++] = pop(s);//ch와 비교하여 우선순위가 낮은 연산자들은 pop하여 후위수식 배열에 넣어준다

				push(s, ch);	//우선순위 낮은 연산자들을 제거하였다면 후위수식 배열에 ch를 넣어라
			}
		}
		else if (ch == '(')	//만약 ch가 (라면 push
			push(s, ch);
		else if (ch == ')') {	//ch가 )라면 (가 나올 때 까지 stack에서 pop하여 후위수식 배열에 추가
			while (top(s) != '(')
				postfix[postfix_idx++] = pop(s);

			pop(s);	// ( 제거
		}
		else {
			while (top(s) != '(' && !is_empty(s) && (compare(ch) <= compare(top(s)))) { // ch가 연산자라면 연산 우선순위 비교
				if (top(s) == '^' && ch == '^')	//다른 연산자와 달리 제곱연산은 오른쪽->왼쪽으로 계산하므로 top이 ^라면 우선순위를 비교하여 pop하지 않고 비교를 종료한다
					break;
				postfix[postfix_idx++] = pop(s);
			}

			push(s, ch); //연산자의 우선순위 비교가 끝났으면 ch를 push한다
		}
	}
	while (!is_empty(s))	// 남아있는 stack을 후위수식에 넣어준다
		postfix[postfix_idx++] = pop(s);

}

void calculate(char* postfix) { // 후위수식 -> 연산하는 함수

	Stack_int operand;
	stack_int_init(&operand);

	for (int i = 0; postfix[i] != '\0'; i++) { // 후위수식 순회
		char ch = postfix[i];

		if (is_operand(ch)) // 피연산자라면
			push_int(&operand, ch - '0');//stack에 넣는다
		else {	//연산자라면 맨 앞에 정수 2개를 pop한다
			int a = pop_int(&operand);
			int b = pop_int(&operand);
			push_int(&operand, do_operator(ch, b, a)); // pop한 정수를 연산한다
		}
	}

	printf("%d\n", pop_int(&operand)); // 연산 후에는 최종결과인 정수 하나 남을 것이다. pop해서 출력한다
}


void stack_char_init(Stack_char* s) { // char형 stack초기화
	s->top = -1;
	s->size = 200;
}

void stack_int_init(Stack_int* s) { //int형 stack 초기화
	s->top = -1;
	s->size = 200;
}

char top(Stack_char* s) {	// char형 top
	return s->arr[s->top];
}

void push(Stack_char* s, char data) {// char형 push
	s->top++;
	s->arr[s->top] = data;
}

void push_int(Stack_int* s, int data) {// int형 push
	s->top++;
	s->arr[s->top] = data;
}

int pop_int(Stack_int* s) { //int형 pop
	int data = s->arr[s->top];
	s->top--;
	return data;
}

char pop(Stack_char* s) {//char형 pop
	char data = top(s);
	s->top--;
	return data;
}

int is_empty(Stack_char* s) { //char형 empty
	return s->top == -1 ? 1 : 0;
}

int compare(char oper) { // 연산자 우선순위 비교 (값 큼 = 우선순위 높음)

	if (oper == '~')
		return 4;
	else if (oper == '^')
		return 3;
	else if (oper == '*' || oper == '/')
		return 2;
	else if (oper == '+' || oper == '-')
		return 1;
}


int is_operand(char ch) { // 연산자 판단
	return (ch >= '0' && ch <= '9') ? 1 : 0;
}

int do_operator(char op, int x, int y) {	// 연산자 계산

	if (op == '~')
		return x * 10 + y;
	else if (op == '^')
		return pow(x, y);
	else if (op == '+')
		return x + y;
	else if (op == '-')
		return x - y;
	else if (op == '*')
		return x * y;
	else if (op == '/')
		return x / y;

}