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

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

 

1. 후기 표기식으로 변환 - 괄호 있는 경우

• 여는 괄호는 무조건 스택에 push ~ 이때 스택 내의 어떤 연산자도 pop X
• 어떤 연산자를 스택에 push 할 때 스택의 top에 여는 괄호가 있으면 아무도 pop하지 않고 그냥 push
• 닫는 괄호가 나오면 스택에서 여는 괄호가 나올 때 까지 pop 해서 출력 ~ 닫는 괄호는 스택에 push X

 

2. 괄호가 있는 후기 표기식으로의 변환 코드

//  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 -> 우선순위가 높을 수록 큰 값
//여는 괄호의 우선순위를 -1로 정의 -> pop하지 않고 무조건 push
static int PRECEDENCE[] = {1, 1, 2, 2, -1, -1};

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

//* 함수 이름 임의 변경 
//- 후위 표기식 계산 is_operator과 중복 && 다른 파일의 is_operator을 사용하면 오류
//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 반환
}

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

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

char *process_op(char op, char *pos){
    //연산자 스택에만 값을 넣지 pos에 추가한 것이 없기 때문에
    //pos의 수정없이 그대로 리턴
    //여는 괄호는 무조건 스택에 push
    if(is_empty(operator_stack) || op == '(')
        push(operator_stack, op);
    else{
        char top_op = peek(operator_stack);
        //여는 괄호는 -1의 우선순위를 가지기 때문에 다른 연산자는 무조건 위에 push됨
        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
                
                //top_op가 여는 괄호일 때, op의 우선순위 <= top_op 라면 op는 닫는 괄호
                if(top_op == '(')
                    break;
                
                sprintf(pos, "%c ", top_op);
                pos += 2;    //연산자 1개와 공백
                if(!is_empty(operator_stack))
                    top_op = (char)peek(operator_stack);
            }
            //닫는 괄호는 스택에 push하지 않는다
            if(op != ')')
                push(operator_stack, op);
        }
    }
    return pos;
}

//모든 토큰들이 공백으로 구분되어 있다고 가정
//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);
        //스택에 여는 괄호가 남아있으면 안된다.
        if(op == '(')
            handle_exception("Unmatched parenthesis.");
        
        sprintf(pos, "%c ", op);
        pos += 2;
    }
    *pos = '\\0';    //마지막에 널 추가
    return postfix;
}

int main(){
    char infix[] = "7 - ( ( 4 + 6 ) / 2 ) * 5";
    char *postfix = convert(infix);
    printf("%s", postfix);
    printf(" = %d\\n", eval(postfix));    //7 4 6 + 2 / 5 * -  = -18
}

 

3. 미흡한 점

• 피연산자는 양의정수만 허용
• 모든 토크들이 공백문자로 구분되어 있어야 함
• 일진(unary) 연산자의 처리: -(-2) = 2
• 왼쪽에서 오른쪽 → 방향의 연산자 처리는 가능하지만, 오른쪽에서 왼쪽 → 방향의 처리를 가지는 연산자는 불가능: right associativity를 가지는 연산자 처리는 불가능
• 후위 표기식으로 변환하는 일과, 계산하는 일을 구분할 필요 없이 하나로 합치기
  • 연산자 스택과 피연산자 스택을 동시에 사용하면서 처리할 수 있다.

 

 

 

 

---

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

https://www.youtube.com/watch?time_continue=1890&v=xeyDpMyn7p4&feature=emb_title