자료구조 - 스택

스택 ADT는 후입선출 방식으로 데이터를 저장, 추출한다. 삽입과 삭제가 일어나는 부분을 탑(top)이라고 명시한다.

스택은 단일연결리스트로 구현이 가능하고 top은 리스트의 맨앞을 가리킨다.

스택은 배열로도 구현이 가능하다. 스택에서의 기본 연산인 push, pop, is_empty에 대해 구현해보자

#include<stdio.h>
int top = -1;
typedef struct stack {
	char oper;
	int order;
}STACK;
void push(STACK stack[], char input, int limit, int order)
{
	if (top >= limit - 1)
	{
		return;
	}
	stack[top + 1].oper = input;
	stack[top + 1].order = order;
	top = top + 1;
}
char pop(STACK stack[])
{
	if (top ==-1)
	{
		return;
	}
	top = top - 1;
	return stack[top + 1].oper;
}
int is_empty()
{
	if (top == -1)
		return 1;
	else return 0;
}   

 

예시 후위수식

우리가 흔히 아는 연산수식은 중위수식이다. 예) 10+3 후위 수식은 컴퓨터가 계산하는 방식이다.

예) 10 3+ -> 10+3 다음 알고리즘은 중위수식을 후위수식으로 전환하는 방법이다.

int priority(char oper, int i,char previous)
{
	if (i == 0&&(oper=='+'||oper=='-'))
		return 6;
	
	switch (oper) {
		case '(':
			return 0;
		case '|':
			return 1;
		case '&':
			return 2;
		case '<':
			return 3;
		case '>':
			return 3;
		case '-':
			if (previous == '+' || previous == '-'||previous=='*'||previous=='/'||previous=='>'||previous=='<'||previous=='&'||previous=='|')
				return 6;
			else
				return 4;
		case '+':
			if (previous == '+' || previous == '-' || previous == '*' || previous == '/' || previous == '>' || previous == '<' || previous == '&' || previous == '|')
				return 6;
			else
				return 4;
		case '/':
			return 5;
		case '*':
			return 5;
		case '!':
			return 6;
	}
}

void main()
{
	STACK stack[101];
	char string[101];
	int num;
	int i, j;


	scanf("%d", &num);
	for (j = 0;j < num;j++)
	{
		top = -1;
		scanf("%s", string);

		for (i = 0;i < strlen(string);i++)
		{
			if (is_operation(string[i],i)==0)
				printf("%c", string[i]);
			else if (string[i] == '(')
					push(stack, string[i], 50,priority(string[i],i,string[i-1]));
			else if (string[i] == ')')
			{
				while (stack[top].oper != '(')
					printf("%c", pop(stack));
				pop(stack);
			}
			else
			{
				while (is_empty() != 1 && stack[top].order >= priority(string[i], i,string[i-1]))
						printf("%c", pop(stack));
				if (string[i] == '|' || string[i] == '&')
				{
					push(stack, string[i], 101, priority(string[i], i, string[i - 1]));
					i++;
				}
				push(stack, string[i], 101, priority(string[i], i, string[i - 1]));
			}
		}
		while (is_empty() != 1)
			printf("%c", pop(stack));
		printf("\n");
	}
	return 0;
}