#20 [C 자료구조] 스택으로 풀 수 있는 문제들

스택을 사용하는 것은 당연히 스택이 쓸모 있는 분야가 있어서다!! 진짜

이 파트에서는 스택이 어떻게 활용되는지, 어떤 방식을 통해 활용할 수 있는지 알아보자.

재밌다고 세뇌해보자

수식 괄호 검사

수식 괄호 검사는 쉽게 말해서 수학 공식에서 소중대 괄호를 사용할 시에 순서대로 맞게 사용했는지 검사하는 알고리즘이다. 

위와 같은 수식에서 우리는 오른쪽 수식들이 잘못되었다는 것을 바로 알 수 있지만 컴퓨터는 몽총해서 에러를 출력한다. 이러한 에러를 출력하기 전에 먼저 올바른 수식인지 여부를 결정하는 함수를 써보자.

크게 논리가 되는 개요는 다음과 같다.

 

{(){()}} 와 같은 수식이 있다고 해보자.

논리는 다음과 같다.

- 직전에 읽은 괄호(왼쪽)와 다음 괄호(오른쪽)가 다른 종류면 에러 처리, 같은 종류(왼쪽 괄호)면 다음 괄호를 읽는다.

- 모든 괄호를 읽은 뒤 에러가 없고 스택이 empty면 정상 아니면 짝이 맞지 않는 것이 있으니 에러 처리!

 

{(){())} 와 같은 수식이 있다고 해보자.

위 식은 마지막 두번 째 ) 에서 오류를 발생한다. 틀린 예시인 것이다.

---

 

 

 

 

수식 계산 및 표기법 변환

스택을 이용해 인간의 방식이 아닌 최대한 컴퓨터에 맞춘 연산 방법으로 표현할 수 있다. 이렇게 하면 훨씬 더 기계적이고 빠르게 계산할 수 있다. 물론 컴퓨터의 입장에서.

이는 방식에 따라 중위 표기법, 후위 표기법, 전위 표기법으로 구분된다.

 

*중위 표기법: 인간이 주로 사용하는 표기법, 괄호 존재

*후위 표기법: 괄호를 없애고 연산자를 피연산자의 뒤에 둠

*전위 표기법: 괄호를 없애고 연산자를 피연산자의 앞에 둠

각각의 예시는 다음과 같다.

괄호 묶기와 연산자 이동은 컴퓨터가 처리하기에 굉장히 비효율적이다. 따라서 우리는 이를 후위 표기법으로 변환하여 코딩해준다. 후위 표기법의 논리적 구성은 다음과 같은 프로세스를 따른다.

 

후위 표기법 변환 방법

보기엔 굉장히 복잡해 보인다. 하지만 논리적 흐름을 따라가면 후위표기법이 훨씬 직관적으로 식을 표현하고 있음을 알 수 있다.

a에서 b를 나누고, c를 뺀 뒤, d와 e를 곱한 것을 더해준다. 그리고 a와 c를 곱한 것을 뺴준다.

사람이 말하는 순서를 그대로 따라가는 모습을 보여준다.

이를 스택의 논리로 구현하면 다음과 같다.

 

스택을 이용한 후위 표기법 변환

1. 좌에서 우로 읽음

2. 피연산자이면, 읽은 문자를 출력

3. 왼쪽 괄호이면, push하여 집어넣음

4. 오른쪽 괄호이면, 왼쪽 괄호가 나올 때까지 pop하고 출력함. 단, 괄호는 출력하지 않음

5. 연산자이면 스택 top(isp)과 자신(icp)의 우선 순위를 비교함. isp<icp이면 push, isp>=icp이면 pop하고 출력함

*isp = in stack precedence / icp = incoming precedence

6. 입력을 모두 읽었으면, 스택이 empty될 때 까지 pop하고 출력함.

 

A * (( B+C ) / D) 의 예시를 통해 다음을 살펴보자

괄호의 pop은 다 없어진다고 보면된다.

여기서 <5. 연산자이면 스택 top(isp)과 자신(icp)의 우선 순위를 비교함. isp<icp이면 push, isp>=icp이면 pop하고 출력함> 의 구문이 제일 헷갈리는데 각 연산자오 괄호는 각각의 isp와 icp값을 가진다.

이를 통해 isp와 icp의 value를 알 수 있는데 위 두 번째 단계에서 *가 push 된 것은 *dml icp=13, isp=0 (eos)이므로 push가 되었다는 것을 알 수 있다.

유사코드로 보자면

If (isp[stack[top]] < icp[token]) --> push

If (isp[stack[top]] >= icp[token]) --> pop until isp[stack[top]] < icp[token]

이런 식이 성립한다.

스택을 이용한 후위 표기법 계산

변환 후 수식을 계산하는 것은 또 다른 작업이 필요하다. 그러나 계산은 굉장히 간단하다.

1) 피연산자는 스택에 PUSH하고

2) 연산자는 2회 POP하여 계산한 후 PUSH한다.

 

8/((3+2)-1) 인 식을 후위표기법으로 변환하면 832+1-/ 이 나온다.

이를 계산해보는 예시는 다음과 같다.

 

---

 

 

 

후위 표기법 변환 코드

논리를 익혔으니 이제 코드로 이를 구현해보자. 전혀 복잡하지 않다. 라고 생각하고 읽어보자.

먼저 후위 표기법 변환을 위한 규칙을 직접 써줘야한다. 저런!

- 후위표기법 규칙 생성

#include <stdio.h>

#define MAX_STACK_SIZE 100 // Max를 항상 지정해둔다.
#define MAX_EXPR_SIZE 100 // expression의 맥스 또한 지정

typedef enum { lparen, rparen, plus, minus, times, divide, mod, eos, operand } precedence;
// precedence 즉 전처리 코드들로 해당 변수들을 지정해준다.

precedence stack[MAX_STACK_SIZE]; // precedence 스트럭쳐를 계승한 stack을 만들었다.

static int isp[] = {0, 19, 12, 12, 13, 13, 13, 0}; // 연산자들 ()+-*/%eos 요것 들의 isp의 값들을 지정해주자
static int icp[] = {20, 19, 12, 12, 13, 13, 13, 0}; //icp값 대입

char expr[MAX_EXPR_SIZE]; // expr에 수식 스트링을 넣어주기 위함이다.
precedence get_token(char *symbol, int *n) {
	*symbol = expr[(*n)++]; //수식에서의 현재 문자를 pop해주는 것이다.
    switch ( *symbol) {
    	case '(' : return lparen;
        case ')' : return rparen;
        case '+' : return plus;
        case '-' : return minus;
        case '/' : return divide;
        case '*' : return times;
        case '%' : return mod;
        case '\0' : return eos;
        default : return operand;
    }
}
        

이와 같이 규칙을 썼으면 이제 실제로 중위 표기법으로 쓰인 것을 후위표기법으로 변환해보자.

 

-후위표기법으로의 변환

void postfix(void) {
    char symbol;
    precedence token;
    int n = 0;
    int top = 0;
    stack[0] = eos; // isp[7]=icp[7]=0
    
    for ( token=get_token(&symbol, &n); token!=eos; token=get_token(&symbol, &n) )
    //토큰이 eos가 될 때 까지 get_token으로 토큰을 대입해본다.
    
    {
    	if ( token == operand ) printf("%c", symbol); // 피연산자이면 출력
    	else if ( token == rparen ) { // unstack tokens until left parenthesis
    		while ( stack[top] != lparen ) print_token(delete(&top));
    		delete(&top); // 오른쪽 괄호면 왼쪽 괄호나올 때까지 pop
    }
    else { 
    	while ( isp[stack[top]] >= icp[token] ) print_token(delete(&top));
    	add(&top, token); // isp>=icp이면 스택에서 pop(삭제) 후 출력
    	}
    }
    while ( (token = delete(&top)) != eos ) print_token(token); // 나머지를pop후출력
    printf("\n");
}

스택을 이용한 후기 표기법 변환을 그대로 코드로 옮겨 적었다.

 

-후위표기법 계산

int eval(void) { // stack, stack top은 전역변수임
    precedence token;
    char symbol;
    int op1, op2;
    int top = -1;
    int n = 0; // 스트링 1개씩 읽어오는 n
    
    token = get_token(&symbol, &n); //토큰을 읽어오자!
    
    while (token != eos) { // eos 전 까지 무한루프
        if (token == operand) // 피연산자이면 숫자로 만들어서 stack top에 삽입
        	add(&top, symbol-’0’);
        else { 				// 연산자이면
        	op2 = delete(&top); // 탑 두개 스택 지우기
        	op1 = delete(&top);
            
        	switch(token) { 	// 연산 후 결과를 스택에 삽입
                case plus: add(&top, op1+op2); break;
                case minus: add(&top, op1-op2); break;
                case times: add(&top, op1*op2); break;
                case divide: add(&top, op1/op2); break;
                case mod: add(&top, op1%op2);
        	}
        }
        token = get_token (&symbol, &n); //다음 토큰으로 넘어가기
    }
    return delete(&top); 
}

---

 

 

 

야심차게 여러 스택을 다루려고 했는데 2개 밖에 다루지 못했다.

내가 글을 쓰다가 머리가 터져버렸으니 다음 포스팅에 다른 스택의 응용 2로 돌아오겠다.