스택(Stack) - 괄호

괄호의 알맞은 짝을 찾을 때 스택을 이용하면 편리하다.

(), [], {}  같은 유형의 괄호들이 사용 되어야 하고 쌍을 이루어야 한다.

다음 3가지 조건을 맞추어 구성되어야 한다.

조건 1 : 왼쪽 괄호의 개수와 오른쪽 괄호의 개수는 같아야 한다.

조건 2 : 같은 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.

조건 3 : 서로 다른 타입의 괄호 쌍이 서로를 교차하면 안된다.

괄호 검사 프로그램 구현

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_STACK_SIZE 100

typedef int Element;


Element data[MAX_STACK_SIZE];

int top;

void error(char str[])
{
	printf("%s\n", str);
	exit(1);
}

void init_stack() { top = -1; }
int is_empty() { return top == -1; }
int is_full() { return top == MAX_STACK_SIZE == -1; }
int size() { return top + 1; }


void push(Element e)
{
	if (is_full())
		error("스택 포화 에러");
	data[++top] = e;
}

Element pop()
{
	if (is_empty())
		error("스택 공백 에러");
	return data[top--];
}

Element peek()
{
	if (is_empty())
		error("스택 공백 에러");
	return data[top];
}

int check_matching(char expr[])
{
	int i = 0, prev;
	char ch;

	init_stack();

	while (expr[i] != '\0') {
		ch = expr[i++];
		if (ch == '[' || ch == '(' || ch == '{')
			push(ch);
		else if (ch == ']' || ch == ')' || ch == '}') {
			if (is_empty())
				return 2; // 조건 2 위반
			prev = pop();
			if ((ch == ']' && prev != '[')
				|| (ch == ')' && prev != '(')
				|| (ch == '}' && prev != '{')) {
				return 3; // 조건 3 위반
			}
		}
	}
	
	if (is_empty() == 0) return 1;  //조건 1 위반
	return 0; // 괄호 정상
}

void main()
{
	char expr[4][80] = { "{A[(i+1)]=0;}", "if((i==0) && (j==0)", "A[(i+1])=0;", "A[i] = f)(;" };
	
	int errCode, i;
	
	for (i = 0; i < 4; i++) {
		errCode = check_matching(expr[i]);
		if (errCode == 0)
			printf(" 정상: %s\n", expr[i]);
		else
			printf(" 오류: %s (조건%d 위반)\n", expr[i], errCode);
	}
}

프로그램 실행 결과

후위 표기 수식 계산

수식 계산에서도 스택이 이용된다. 

수식은 연산자와 피연산자를 이용해 나타내는데, 이들의 상대적인 위치에 따라 다음과 같이 나눌 수 있다.

전위 표기법(prefix): 연산자를 피연산자 앞에 표기한다.

ex) +AB, +5*AB

중위 표기법(infix): 연산자를 피연산자 사이에 표기한다.

ex) A+B, 5+A*B

후위 표기법(postfix): 연산자를 피연산자 뒤에 표기한다.

ex) Ab+, 5AB*+

우리는 중위 표기법에 익숙하지만 컴파일러는 후위 표기법을 좋아한다. 

그 이유는 후위 표기 수식이 컴퓨터 입장에서 여러가지 장점을 갖고 있다. 

중위 표기 수식 ( A + B ) * C 에서 괄호는 더하기 연산이 곱하기 연산보다 먼저 수행되어야 한다.

이에 대해 후위 표기식은 A B + C * 이다. 이 표기법을 사용함으로써 여러가지 장점을 갖는다.

1. 괄호를 사용하지 않고도 계산해야 할 순서를 알 수 있다.

2. 연산자의 우선순위를 생각할 필요가 없다. 식 자체에 우선순위가 이미 포함되어 있기 때문이다.

3. 수식을 읽으면서 바로 계산이 가능하다. 중위 표현식은 괄호와 연산자의 우선순위 때문에 수식을 끝까지 읽은 다음에야 계산이 가능하다.

컴파일러는 이러한 장점 때문에 프로그램 개발자가 입력한 중위 표기 수식을 후위 표기 수식으로 바꾸고, 변환된 후위 표기 수식을 계산하는

방법을 사용한다. 먼저 후위 표기 수식을 계산하는 방법을 살펴보고, 중위 표기 수식을 후위 표기법으로 변환하는 방법도 알아본다.

후위 표기 수식의 계산 알고리즘

후위 표기 수식의 계산에도 스택이 사용된다. 계산을 위해 전체 수식을 왼쪽에서 오른쪽으로 스캔하는데, 스캔 과정에 피연산자가 나오면

무조건 스택에 저장한다. 연산자가 나오면 스택에서 피연산자 두 개를 꺼내 연산을 실행하고 그 결과를 다시 스택에 저장한다. 이 과정을 

수식이 모두 처리될 때 까지 반복되고, 마지막으로 스택에는 최종 계산 결과만 하나 남는다.

후위 표기 수식 계산 프로그램 구현

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_STACK_SIZE 100

typedef double Element;


Element data[MAX_STACK_SIZE];

int top;

void error(char str[])
{
	printf("%s\n", str);
	exit(1);
}

void init_stack() { top = -1; }
int is_empty() { return top == -1; }
int is_full() { return top == MAX_STACK_SIZE == -1; }
int size() { return top + 1; }


void push(Element e)
{
	if (is_full())
		error("스택 포화 에러");
	data[++top] = e;
}

Element pop()
{
	if (is_empty())
		error("스택 공백 에러");
	return data[top--];
}

Element peek()
{
	if (is_empty())
		error("스택 공백 에러");
	return data[top];
}

double calc_postfix(char expr[])
{
	char c;
	int i = 0;
	double val, val1, val2;

	init_stack();
	while (expr[i] != '\0') {
		c = expr[i++];
		if (c >= '0' && c <= '9') {
			val = c - '0';
			push(val);
		}
		else if (c == '+' || c == '-' || c == '*' || c == '/') {
			val2 = pop();
			val1 = pop();
			switch (c) {
			case '+': push(val1 + val2); break;
			case '-': push(val1 - val2); break;
			case '*': push(val1 * val2); break;
			case '/': push(val1 / val2); break;
			}
		}
	}
	return pop();
}

void main()
{
	char expr[2][80] = { "8 2 / 3 -3 2 * +", "12/4*14/*" };

	printf("수식: %s = %lf\n", expr[0], calc_postfix(expr[0]));
	printf("수식: %s = %lf\n", expr[1], calc_postfix(expr[1]));

}

중위 표기의 후위 표기 변환 알고리즘

두 표기식의 공통점은 피연산자의 순서가 동일하다는 것이다.(연산자들의 순서는 달라진다.)

연산자의 출력 순서는 연산자들의 우선순위 관계와 괄호에 의해 결정되며 후위표기 변환에도 스택이 사용된다.

1. 입력된 중위 표기 수식을 순서대로 하나씩 스캔한다.

2. 피연산자를 만나면 바로 (후위 표기식으로) 출력하면 된다.

3. 연산자를 만나면 어딘가에 잠시 저장해야 한다. 후위 표기에서는 연산자가 피연산자들 뒤에 나오기 때문이다. 다라서 적절한 위치를 찾을 

때 까지 출력을 보류하여야 한다. 연산자의 저장에는 스택이 사용된다.

중위 수식의 후위 표기 변환 프로그램

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_STACK_SIZE 100

typedef int Element;


Element data[MAX_STACK_SIZE];

int top;

void error(char str[])
{
	printf("%s\n", str);
	exit(1);
}

void init_stack() { top = -1; }
int is_empty() { return top == -1; }
int is_full() { return top == MAX_STACK_SIZE == -1; }
int size() { return top + 1; }


void push(Element e)
{
	if (is_full())
		error("스택 포화 에러");
	data[++top] = e;
}

Element pop()
{
	if (is_empty())
		error("스택 공백 에러");
	return data[top--];
}

Element peek()
{
	if (is_empty())
		error("스택 공백 에러");
	return data[top];
}

int precedence(char op)
{
	switch (op) {
	case '(': case ')': return 0;
	case '+': case '-': return 1;
	case '*': case '/': return 2;
	}
	return -1;
}

void infix_to_postfix(char expr[])
{
	int i = 0;
	char c, op;

	init_stack();

	while (expr[i] != '\0') {
		c = expr[i++];
		if ((c >= '0' && c <= '9')) {
			printf("%c ", c);
		}
		else if (c == '(')
			push(c);
		else if (c == ')') {
			while (is_empty() == 0) {
				op = pop();
				if (op == '(') break;
				else printf(" %c ", op);
			}
		}
		else if (c == '+' || c == '-' || c == '*' || c == '/') {
			while (is_empty() == 0) 
				{
					op = peek();
					if (precedence(c) <= precedence(op)) {
						printf(" %c ", op);
						pop();
					}
					else break;
				}
				push(c);
			}
		}
		while (is_empty() == 0)
			printf("%c ", pop());
		printf("\n");
}

void main()
{
	char expr[2][80] = { "8 / 2 - 3 + (3 * 2)", "1 / 2 * 4 * (1/4)" };

	printf("중위수식: %s ==> 후위수식:", expr[0]);
	infix_to_postfix(expr[0]);
	printf("중위수식: %s ==> 후위수식:", expr[1]);
	infix_to_postfix(expr[1]);
}