[자료구조] 스택을 응용, 활용한 프로그램

스택을 응용한 예시로는 괄호 검사, 

 

스택의 응용1 : 괄호 검사 프로그램

괄호의 종류에는 대괄호 [ , ] 중괄호 { , } 소괄호 ( , ) 가 있습니다.

 

프로그램을 구현하기 위해 다음 조건을 만족해야 합니다.

  1. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.

  2. 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.

  3. 괄호 사이에는 포함 관계만 존재한다.

 

검사가 필요해 보이는 잘못된 괄호 사용의 예시

  (a(b)

  a(b)c)

  a{b(c[d]e}f)

 

알고리즘

문자열에 있는 괄호를 차례대로 조사하면서 왼쪽 괄호를 만나면 스택에 삽입하고, 오른쪽 괄호를 만나면 스택에서 삭제한 후 짝이 맞는지를 검사합니다.

이 때, 스택이 비어 있으면 조건1 또는 조건2 등을 위배하게 되고 괄호의 짝이 맞지 않으면 조건3 등에 위배됩니다.

마지막 괄호까지를 조사한 후에 스택이 비어 있으면 1(참)을 반환하고, 그렇지 않으면 조건 1에 위배되므로 0(거짓)을 반환합니다.

 

int check_matching(const char *in) { // 문자열
	StackType s; // 스택 선언
	char ch, open_ch; // ch : 들어온 문자열의 문자, open_ch : pop()으로 꺼낸 문자
	int i, n = strlen(in); 
	init_stack(&s);	// s의 top을 -1로 초기화
	for (i = 0; i < n; i++) {
		ch = in[i];	
		switch (ch) {
		case '(':   case '[':    case '{': // ch값이 왼쪽 괄호라면
			push(&s, ch); 
			break;
		case ')':   case ']':    case '}': // ch값이 오른쪽 괄호라면
			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;
}

// 실행결과
{A[(i+1)]=0;} 괄호검사성공

 

 

 

스택의 응용2 : 수식 표기 및 계산

수식의 표기 방법에는 3가지가 존재합니다.

 

중위 표기법

2+3*4   a*b+5   (1+2)*7

전위 표기법

+2*34   +*ab5   *+127

후위 표기법

234*+   ab*5+   12+7+

 

컴퓨터가 수식을 계산하는 순서는 다음과 같으며 모두 스택을 이용합니다

중위표기식 -> 후위표기식 ->계산 

2+3*4 -> 234*+ -> 14

 

 

후위 표기법을 계산하는 방법

기본적으로 수식을 왼쪽에서 오른쪽으로 스캔합니다.

피연산자

>> 스택에 저장

연산자

>> 필요한 수 만큼의 피연산자를 스택에서 꺼내 연산을 실행하고 연산의 결과를 다시 스택에 저장

 

예시 82/3-32*+ 를 살펴봅시다.

>> 8과 2를 스택에 넣고 / 연산 실행한 값 4를 스택에 다시 넣습니다.

>> 3을 스택에 넣고 4와 3을 - 연산 실행한 값 1을 스택에 다시 넣습니다.

>> 3과 2를 스택에 넣고 * 연산 실행한 값 6을 스택에 다시 넣습니다.

>> 1과 6을 + 연산 실행한 값 7을 스택에 다시 넣습니다.

최종 연산 결과는 7이 됩니다.

 

int eval(char exp[])
{	
	int op1, op2, value, i = 0;
	int len = strlen(exp);
	char ch;
	StackType s;
	init_stack(&s);
	for (i = 0; i < len; i++) {
		ch = exp[i];
		if (ch != '+' && ch != '-' && ch != '*' && ch != '/') {	// 입력이 피연산자이면
		    value = ch - '0';
                    push(&s, value);
		}
		else {	// 입력이 연산자이면
			op2 = pop(&s); op1 = pop(&s);	//피연산자를 스택에서 제거
			switch (ch) {	//연산을 수행하고 스택에 저장 
				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); 
}

후위 표기식 알고리즘을 프로그램으로 구현해봅시다. 

 

먼저 입력이 피연산자인 경우를 살펴보면 ch는 들어온 문자열 exp[]의 요소가 하나씩 저장됩니다. 알아두어야 할 점은 ch는 자료형이 char입니다. ch가 피연산자인 경우 value에 ch - '0' 을 한 값을 저장하게 됩니다. value의 자료형은 int입니다. 즉, 여기에서 ASCII TABLE에 대한 개념이 필요한데 자세한 정보는 설명되어 있는 곳이 많으니 여기서는 생략하겠습니다.

ch값이 만약 문자 '7' 이라면 '7'은 ASCII 값으로 숫자 87입니다. 그러므로 value를 숫자 7로 저장하기 위해선 '0'의 ASCII 값 80을 빼주는 것이죠. (87 - 80 == 7). 그리하여 스택에는 정수 value가 저장되는 것입니다.

 

입력이 연산자인 경우를 살펴보면 연산을 실행하기 위해 2개의 수가 필요하기 때문에 스택에서 값을 2개 꺼내서 op2와 op1에 각각 저장합니다. switch case 문에 의해 연산을 실행한 결괏값을 스택에 다시 삽입합니다.

 

이후 최종 반환값으로 스택에 남아있는 최종 연산된 값을 반환합니다

 

 

 

중위 표기식을 후위 표기식으로 변경하기

중위 표기법과 후위 표기법의 공통점은 피연산자의 순서가 동일하다는 것입니다. 따라서 연산자들의 순서만 다르기 때문에(우선순위순서) 연산자만 스택에 저장했다가 출력하면 된다.

// 연산자의 우선순위를 반환한다.
int prec(char op)
{
	switch (op) {
		case '(': case ')': return 0;
		case '+': case '-': return 1;
		case '*': case '/': return 2;
	}
	return -1;
}

// 중위 표기 수식 -> 후위 표기 수식 변환 함수
void infix_to_postfix(char exp[])  { 
	int i = 0;
	char ch, top_op;
	int len = strlen(exp); 
	StackType s;
	init_stack(&s);	
	for (i = 0; i < len; i++) {
		ch = exp[i];
		switch (ch) {
			case '+': case '-': case '*': case '/': // ch가 연산자일때
				while (!is_empty(&s) && (prec(ch) <= prec(peek(&s))))
					printf("%c", pop(&s)); 
				push(&s, ch);  break;
			case '(':	
                                push(&s, ch);  
                                break; 
			case ')':	
				top_op = pop(&s); 
				while (top_op != '(') { // top_op가 오른쪽 괄호를 만날때까지
					printf("%c", top_op);
					top_op = pop(&s);
				}
				break;
			default:	printf("%c", ch);  break;  // ch가 피연산자인 경우
		}
	}
	while (!is_empty(&s))
		printf("%c", pop(&s));  //  스택에 저장된 연산자(값)들을 하나씩 꺼내서 출력
}

int main(void)
{
	char *s = "(2+3)*4+9";
	printf("중위표시수식 %s \n", s);
	printf("후위표시수식 ");
	infix_to_postfix(s);
	printf("\n");
	return 0;
}

// 실행결과
중위표시수식 (2+3)*4+9
후위표시수식 23+4*9+

 

 

 

스택을 활용하여 문자열 회문 여부 검사하기

회문이란 level, abccba 처럼 거꾸로 써도 같은 문자열인 것을 말합니다.

#include <stdio.h>
#define MAX_SIZE 50
typedef struct {
	char word[MAX_SIZE];
	int top;
} StackType;

void init_stack(StackType* s) {
	s->top = -1;
}
int is_full(StackType* s) {
	return (s->top + 1) == MAX_SIZE;
}
int is_empty(StackType* s) {
	return s->top == -1;
}
void push(StackType* s, char word) {
	if (is_full(s)) {
		printf("스택 포화 에러");
	}
	else {
		s->top++;
		s->word[s->top] = word;
	}
}
char pop(StackType* s) {
	int temp;
	if (is_empty(s)) {
		printf("스택 공백 에러");
		return 0;
	}
	temp = s->word[s->top];
	s->top--;
	return temp;
}
int palindrome(char str[]) {
	StackType s;
	init_stack(&s);
	for (int i = 0; str[i] != 0; i++) {
		push(&s, str[i]);
	}
	for (int i = 0; str[i] != 0; i++) {
		if (str[i] != pop(&s)) return 0;
	}
	return 1;
}
int main() {
	char input[MAX_SIZE];
	printf("입력 단어 : ");
	gets(input);
	if (palindrome(input)) {
		printf("회문입니다");
	}
	else {
		printf("회문이 아닙니다");
	}
	return 0;
}