[자료구조 - C언어] 자료구조 제16강: 스택의 응용 - 후위표기식(2), (3)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

1. infix expression → post expression

• 중위(infix) 표기식은 연산자들 간의 우선순위도 고려해야 한다.
• 후위(postfix) 표기식은 피연산자는 스택에 push, 연산자가 나오면 pop

  7 - 4 * 3 * 1 + 5 = 7 4 3 * 1 * - 5 + = 0

  • 중위 표기식 보다 간단하다.
  • 그래서 중위 표기식 입력 → 후기 표기식으로 변환
    • 후기 표기식에서는 (중위 표기식과 다르게)
      • 괄호가 없다.
      • 연산자는 등장하는 순서대로 계산
      • 중위, 후위 모두 피연산자의 순서는 보존
      • 후위는 중위에 비해 연산자가 뒤로 이동

 

2. 후위 표기식으로 변환 - 괄호 없는 경우

• 중위 표기식을 처음부터 순서대로 읽으면서
  • 피연산자는 즉시 출력
  • 모든 연산자는 즉시 출력할 수 없어 일단 스택에 push한다.
    • 예) 2 - 10 에서 피연산자 10이 출력되기 전에 연산자 - 가 출력될 수 없다.
    • push 하기 전에 스택에 우선순위가 자신보다 더 높은 연산자가 있으면 pop 하여 출력한 후 push
      • ( * , / )와 ( + , - )는 우선순위가 각각 동일하다 → 먼저 나온 연산자의 우선순위가 높다
• 수식이 종료되면 스택에 있는 모든 연산자를 pop 하여 출력

2-1. infix expression → postfix expression

(1) 변환된 postfix를 저장할 string을 초기화

     (2) 연산자 스택을 생성

     (3) while(infix에 남은 문자가 있을 때까지)

         (4) infix에서 토큰을 받아서

         (5) 토큰이 피연산자라면

             (6) postfix에 저장(=출력)

         (7) 토큰이 연산자라면

             (8) 연산자를 처리하는 함수 호출(= process_operator)

         (9) 토큰이 피연산자도 아니고 연산자도 아니라면

             (10) 문법적 오류

     (11) 연산자 스택에 남아있는 연산자들을 pop 해서 postix에 추가

2-2. 연산자를 처리하는 함수 호출 process_operator

• 현재 연산자: cur_op
• 가장 위에 있는 연산자: top_op

(1) 연산자 스택이 비었다면

     (2) cur_op를 연산자 스택에 push

(3) 연산자 스택이 비어있지 않다면

     (4) 연산자 스택에서 가장 위에 있는 연산자(= top_op)를 peek

     (5) cur_op의 우선순위 > top_op의 우선순위 라면

          (6) 연산자 스택에 cur_op를 push

     (7) 그렇지 않다면

          (8) whlie(cur_op의 우선순위 ≤ top_op의 우선순위)
               (우선순위가 같은 경우에도 스택 안에 있는 연산자가 더 높은 우선순위를 가짐)

               (9) top_op를 pop → postfix에 append

               (10) 연산자 스택이 비어있지 않다면

                    (11) 연산자 스택에서 peek 해서 새로운 top_op 저장

     (12) 연산자 스택에 cur_op를 push

 

3. 괄호 없는 후기 표기식으로의 변환 코드

• #include “stackADT.h” 사용

//  infix_to_postfix.c

#include <stdio.h>
#include "stackADT.h"

struct stack_type{
    Item *contents;    //배열
    int top;           //스택의 top을 가리키는 변수
    int size;          //배열의 크기
};

static char OPERATORS[] = "+-*/";
//연산자의 우선순위 배열 + - * / 1 1 2 2 -> 우선순위가 높을 수록 큰 값
static int PRECEDENCE[] = {1, 1, 2, 2};

//연산자들이 저장될 스택
//int 스택
Stack operator_stack;


int precedence(char op){
    //is_operator의 리턴값은 +는 0, -는 1, *는 2, /는 3
    //PRECEDENCE는 +는 1, -는 1, *는 2, /는 2를 리턴
    return PRECEDENCE[is_operator(op)];
}


//ch가 연산자인지 아닌지를 검사하는 함수, 연산자가 아니라면 -1 반환
int is_operator(char ch){
    for(int i=0;i<strlen(OPERATORS); i++)
        if(OPERATORS[i] == ch)
            return  i;    //+는 0, -는 1, *는 2, /는 3
    return -1;          //연산자가 아니라면 -1 반환
}


void handle_exception(const char *err_msg){
    printf("%s\\n", err_msg);
    exit(1);
}


//모든 토큰들이 공백으로 구분되어 있다고 가정
//infix -> postfix expression
char *convert(char *infix){
    operator_stack = create();
    
    //변환된 postfix expression이 저장될 문자배열 -> 리턴해야하기 때문에 시작 주소를 저장
    //infix + 1 -> 배열이기 때문에 strlen보다 1칸 더 길어야 한다. '\0' 저장
    char *postfix = (char *)malloc(strlen(infix) + 1);
    char *pos = postfix;    //pos는 postfix 어디가 비었는지를 알려주는 역할
    
    char *token = strtok(infix, " ");
    while(token != NULL){
        //피연산자
        if(token[0] >= '0' && token[0] <= '9'){
            //pos위치에 "%s "포멧스트링으로 token값을 문자열에 append
            sprintf(pos, "%s ", token);
            pos += (strlen(token) + 1);        //공백문자 1 만큼 더 뒤로 이동
        }
        //연산자
        else if(is_operator(token[0]) > -1){
            //c언어는 값에 의한 전달이기 때문에 매개변수를 수정한다 한들 원래 값에 반영되지 않음
            //그렇기 때문에 매개변수를 pos를 주고 리턴값으로
            //연산자를 append한 후의 문자열의 끝 주소를 받아 pos(원래 값)에 저장
            pos = process_op(token[0], pos);
        }
        else{
            handle_exception("Syntax Error: invalid character encountered.");
        }
        token = strtok(NULL, " ");
    }
    //연산자 스택에 남아있는 연산자를 처리
    while(!is_empty(operator_stack)){
        char op = (char)pop(operator_stack);
        sprintf(pos, "%c", op);
        pos += 2;
    }
    *pos = '\0';    //마지막에 널 추가
    return postfix;
}


char *process_op(char op, char *pos){
    //연산자 스택에만 값을 넣지 pos에 추가한 것이 없기 때문에
    //pos의 수정없이 그대로 리턴
    if(is_empty(operator_stack))
        push(operator_stack, op);
    else{
        char top_op = peek(operator_stack);
        if(precedence(op) > precedence(top_op))
            push(operator_stack, op);    //pos의 수정없이 그대로 리턴
        else{
            while(!is_empty(operator_stack) && precedence(op) <= precedence(top_op)){
                pop(operator_stack);    //top_op에 값을 저장하고 있기 때문에 pop한 값은 저장 X
                sprintf(pos, "%c ", top_op);
                pos += 2;    //연산자 1개와 공백
                if(!is_empty(operator_stack))
                    top_op = (char)peek(operator_stack);
            }
            push(operator_stack, op);
        }
    }
    return pos;
}


int main(){
    char infix[] = "7 - 4 * 3 * 1 + 5";
    char *postfix = convert(infix);
    printf("%s", postfix);    //7 4 3 * 1 * - 5 +
}

• stackADT.h

//  stackADT_.h

#ifndef STACKADT_H
#define STACKADT_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

//re-definition, 별명을 만들어 줌, int를 Item이라고 부르겠다.
typedef int Item;

typedef struct stack_type *Stack;

Stack create();
void destroy(Stack s);
void make_empty(Stack s);
bool is_empty(Stack s);
void push(Stack s, Item i);
Item pop(Stack s);
Item peek(Stack s);
void reallocateStack(Stack s);

int is_operator(char ch);
int eval_op(char op);
void handle_exception(const char *err_msg);

bool is_full(Stack s);
void printStack(Stack s);
#endif /* STACKADT_h */

• stackADT_array.c (스택 기본 함수 정의 파일) - 자료구조 제 15강 참고

//  stackADT.c


#include "stackADT.h"

#define INIT_CAPACITY 100

//contents, top, size를 하나의 스택으로
struct stack_type{
    Item *contents;            //배열
    int top;                        //스택의 top을 가리키는 변수
    int size;                        //배열의 크기
};

void reallocateStack(Stack s);

//예외적 상황에 대한 메세지 출력 함수
//static 함수 - 해당 파일 내에서만 호출할 수 있는 함수
//->같은 이름의 함수를 여러 개의 파일에서 생성할 수 있어 충돌을 방지
static void terminate(const char *message){
    printf("%s\n", message);
    exit(1);    //종료
}

//스택을 만들어서 주소를 리턴해주는 함수
Stack create(){
    //Stack 자체가 struct stack_type *로 정의했기 때문에 '(Stack *)'를 사용하지 않아도 됨
    //Stack * 타입이 아니라 Stack 타입 -> Stack 자체가 struct stack_type *으로 정의했기 때문
    Stack s = (Stack)malloc(sizeof(struct stack_type));
    if(s==NULL)
        terminate("Error in create: stack could not be created.");
    
    //스택 자체만 생성해서는 안되고, 내부의 contents에 달려 있는 배열도 동적 할당으로 생성
    s->contents = (Item *)malloc(INIT_CAPACITY * sizeof(Item));
    if(s->contents == NULL){
        free(s);
        terminate("Error in create: stack could notebe created.");
    }
    s->top = -1;
    s->size = INIT_CAPACITY;
    return s;    //동적으로 생성된 s의 주소를 리턴
}

//스택이 필요 없어 졌을 때 free해서 가비지 문제 해결
void destroy(Stack s){
    free(s->contents);
    free(s);
}

//스택의 내용만 비우는 함수, 스택을 다른 용도로 사용하기 위해서 스택을 초기화
void make_empty(Stack s){
    s->top = -1;
}

//스택이 비었는지 검사하는 함수
bool is_empty(Stack s){
    return s->top == -1;
}

//임의로 생성
bool is_full(Stack s){
    return s->top + 1 == s->size;
}
//임의로 생성
void printStack(Stack s){
    for(int i=s->top; i>-1; i--){
        printf(" %d", s->contents[i]);
    }
    printf("\n");
}

void push(Stack s, Item i){
    if(is_full(s))
        reallocateStack(s);
    s->top++;
    s->contents[s->top] = i;
}

Item pop(Stack s){
    if(is_empty(s))
        terminate("Error in pop: stack is empty.");
    s->top--;
    //top을 감소시키고, 감소시키기 전의 위치를 반환
    return s->contents[s->top+1];
}

Item peek(Stack s){
    if(is_empty(s))
        terminate("Error in peek: stack is empty.");
    return s->contents[s->top];
}

//스택이 꽉 찼을 때 reallocate
void reallocateStack(Stack s){
    //현재 사이즈의 2배 크기의 메모리를 malloc
    Item *tmp = (Item *)malloc(2 * s->size * sizeof(Item));
    if(tmp==NULL)
        terminate("Error in create: stack could not be created.");
    //현재 배열내의 데이터를 새로운 배열로 복사하고
    for(int i=0; i<s->size;i++)
        tmp[i] = s->contents[i];
    //필요 없어진 s는 free
    free(s->contents);
    //스택의 contents는 새로 생성된 tmp, 사이즈는 2배 증가
    s->contents = tmp;
    s->size *= 2;
}


//후위표기식 계산


//이 프로그램이 지원하는 연산자들을 하나의 String에 모아둠
static char OPERATORS[] = "+-*/";
//피연산자들을 저장할 스택
Stack operand_stack;

//ch가 연산자인지 아닌지를 검사하는 함수, 연산자가 아니라면 -1 반환
int is_operator(char ch){
    for(int i=0;i<strlen(OPERATORS); i++)
        if(OPERATORS[i] == ch)
            return  i;    //+는 0, -는 1, *는 2, /는 3
    return -1;          //연산자가 아니라면 -1 반환
}

void handle_exception(const char *err_msg){
    printf("%s\n", err_msg);
    exit(1);
}

//입력으로 하나의 연산자를 받아, 스택에서 pop을 2번한 연산결과를 리턴하는 함수
int eval_op(char op){
    //pop하기 전에 스택이 비었는지 확인
    //첫 번째 pop: right hand side: 오른쪽 피연산자
    if(is_empty(operand_stack))
        handle_exception("Syntax Error: 1Stack empty in eval_op");
    int rhs = pop(operand_stack);
    
    //두 번째 pop: left hand side: 왼쪽 피연산자
    if(is_empty(operand_stack))
        handle_exception("Syntax Error: 2Stack empty in eval_op.");
    int lhs = pop(operand_stack);
    
    int result = 0;
    switch(op){
        case '+': result = lhs + rhs; break;
        case '-': result = lhs - rhs; break;
        case '*': result = lhs * rhs; break;
        case '/': result = lhs / rhs; break;
    }
    return result;
}


//*expr은 후위표기식이 하나의 문자열의 형태로 주어졌을 때 계산하는 함수
int eval(char *expr){
    operand_stack = create();    //operand_stack은 stack 객체에 대해 주소를 저장하는 포인터
    char *token = strtok(expr, " ");    //모든 연산자와 피연산자가 공백문자로 구분되어 있다고 가정
    while(token != NULL){
        //피연산자 - 스택에 push
        if(token[0]>='0' && token[0] <= '9'){
            int value = atoi(token);    //문자열로 표현된 수 -> 정수 변환
            push(operand_stack, value);
        }
        //연산자
        else if(is_operator(token[0]) > -1){
            int result = eval_op(token[0]);    //연산자를 계산하는 별개의 함수
            push(operand_stack, result);     //연산결과 스택에 push
        }
        else{
            handle_exception("Syntax Error: invalid character encountered.");
        }
        token = strtok(NULL, " ");
    }    //while문이 끝나면 입력된 후위표기식 수식에 대한 처리가 끝남
          //-> 스택에는 하나의 값만 남아야함
    
    if(is_empty(operand_stack))
        handle_exception("Syntax Error: Stack empty in eval_op.");
    
    int answer = pop(operand_stack);
    //남은 하나의 값을 pop한 후에도 스택이 비어있지 않다면 - 수식 오류
    if(is_empty(operand_stack))
        return answer;
    else{
        handle_exception("Syntax Error: Stack should be empty.");
        return -1;
    }
}

  

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://www.youtube.com/watch?time_continue=1317&v=z3EARoUZ4-0&feature=emb_title 

https://www.youtube.com/watch?v=84Rc4w7YiTc