[자료구조][C언어]스택이란?(4)_후위 표기식의 계산

저번 시간에는 스택을 활용하여 수식의 괄호가 유효한지에 대해 검사하는 프로그램을 만들었다.

이번 시간에는 스택을 활용하여 후위 표기식을 계산하는 방법에 대해 알아보도록 하자.

 

스택의 활용 2_ 후위 표기식의 계산

 

배경지식

후위 표기식의 계산을 하기 전에 후위 표기 식이 뭔지 알아보자.
먼저, 수식을 표현하는 방법에는 전위 표기법, 중위 표기법, 후위 표기법이 있다.

 

전위 표기법은 연산자를 먼저 표시하고 피연산자를 나중에 표시한다.

ex) +AB, +2*34, *+127

 

중위 표기법은 피연산자 사이에 연산자를 표시하는 방법이다.

괄호로 우선순위를 표시한다.

주로 일상 속에서 흔히 사용하는 방법이다.

ex) A+B, 2+3*4, (1+2)*7

 

후위 표기법은 피연산자를 먼저 표기하고 연산자를 뒤에 표기하는 방법이다.

괄호로 우선순위를 표시하지 않고 순서에 따라 우선순위가 나타난다.

ex) AB+, 234*+, 12+7*

ex) (1+2)*7을 후위 표기식으로 바꾸면 12+7*이다.

1+2*7을 후위 표기식으로 바꾸면 127*+이다.

 

후위 표기식을 계산하기 위해서는 앞에서 읽어나가다 연산자가 나오면

앞의 두 피연산자를 해당 연산자로 연산해주고 그 값을 저장하고 계속 읽다가

연산자가 나오면 해당 연산자로 앞의 두 피연산자를 연산해주면 된다.

 

ex) 234*+의 경우, 2,3,4, 그리고 연산자인 * 가 나오는데 이때 앞의 두 피연산자인 3과 4를 연산해주면

3*4 = 12이 된다. 위 식은 2(12)+가 된다. 똑같이 다시 읽어나가면 2와 12를 + 연산해주면 된다.

 

요약하자면 입력을 계속 받으면서, 피연산자는 스택에 받고 연산자가 입력으로 올 경우 이전에 입력된 피연산자 둘을 연산하고 스택에 집어넣고 피연산자가 오면 스택에 받고 연산자가 입력으로 올 경우 이전에 입력된 숫자 둘을 연산자로 계산해주고 입력이 끝날 때까지 위 과정을 계속 반복한다. 

 

위 과정은 다음과 같이 스택으로 쉽게 구현이 가능하다.

 

후위 표기식의 계산1

 

후위 표기식의 계산2

후위 표기식의 계산3

 

1. 피연산자 2를 스택에 삽입한다.

 

2. 피연산자 3을 스택에 삽입한다.

 

3. 피연산자 4를 스택에 삽입한다.

 

4. 연산자 * 를 만났으므로 스택의 상위 2개의 값인 4와 3을

스택에서 꺼내고 연산자와의 연산 결과를 스택에 집어넣는다.(4 * 3 = 12)

 

5. 연산자 + 를 만났으므로 스택의 상위 2개의 값인 12와 2를 꺼내고

해당 연산자와의 결과를 스택에 집어넣는다.(12+2 = 14)

 

6. 입력이 끝났다. 스택에 남아있는 값이 후위 표기식의 계산 결과이다.

 

후위 표기식의 계산 구현

 

먼저, 전에 만들었던 스택 구조체를 가져온다.

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define SIZE 100
typedef struct StackType{
    int top;
    int elem[SIZE];
}StackType;

void init(StackType *S){
    S->top = -1;
}

int isFull(StackType *S){
    return S->top == SIZE - 1;
}

int isEmpty(StackType *S){
    return S->top == -1;
}
void push(StackType *S,int e){
    S->elem[++S->top] = e;
}

int peek(StackType *S){
    if(isEmpty(S)){
        return -1;
    }
    int top = S->elem[S->top];
    return top;
}

int size(StackType *S){
    int size = S->top+1;
    return size;
}

int pop(StackType *S){
    if(isEmpty(S))
        return -1;
    else{
        int e = S->elem[S->top--];
        return e;
    }
}

void printStack(StackType *S){
    if(isEmpty(S)){
        return;
    }
    else{
        printf("Stack:");
        for(int i = 0; i <= S->top; i++){
            printf(" %d",S->elem[i]);
        }
    printf("\n");
    }
    
}

void SumOfStack(StackType *S){
    unsigned int sum = 0;
    for(int i = 0; i <= S->top; i++){
        sum += S->elem[i];
    }
    printf("%d",sum);
}

후위 표기식을 계산하는 알고리즘을 구현하면 다음과 같다.

void postfix(char str[]){
    StackType S;
    init(&S);
    int n = strlen(str);
    for(int i = 0; i < n; i++){
        //입력이 연산자가 아니라 피연산자라면
        if(str[i]!='+' && str[i]!='-'&& str[i]!='*'&& str[i]!='/'){
            push(&S,str[i]-'0');
        }
        else{
            int var1 = pop(&S);
            int var2 = pop(&S);
            switch(str[i]){
            case '+': push(&S,var1+var2);break;
            case '-': push(&S,var1-var2);break;
            case '*': push(&S,var1*var2);break;
            case '/': push(&S,var1/var2);break;
            }
        }
    }
    printStack(&S);
}


int main()
{
    char str[10] = "234*+";
    postfix(str);
    
    return 0;
}

혹시 잘못되거나 궁금한 점이 있다면 언제든지 댓글을 달아 주시면 감사하겠습니다!!

 

참조

천인국 외 2인 , C언어로 쉽게 풀어쓴 자료구조, 생능출판, 2019

심심231, " [Algorithm]전위/중위/후위표기법(prefix/infix/postfix)".1.31.2020. https://simsim231.tistory.com/54