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

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

 

1. 후위 표기식(postfix expression)

• 중위 표기식: 연산자가 피연산자의 사이에 들어감, 일반적으로 사용하는 수식의 표기법
  • 4 x ( 7 + 2 ) = 36
• 후위 표기식:연산자가 피연산자 뒤에 나옴
  • 4 7 2 + x = 36
  • 연산자가 나오면(+) 연산자 바로 앞의 두 피연산자(7, 2)를 계산하고
    → 4 9 x : 연산자가 나오면(x) 연산자 바로 앞의 두 피연산자(4, 9)를 계산 = 36

 

2. 후위 표기식 계산 방법

• 모든 피연산자는 양의 정수라고 가정
• 모든 연산자와 피연산자 사이에는 공백 문자가 있다고 가정

(1) 정수형 빈 스택을 생성

(2) while(토큰이 남아있을 때)

    (3) 다음 토큰으로 이동해서

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

        (5) 스택에 push

    (6) 토큰이 연산자라면

        (7) 스택에서 pop 하고 오른쪽 피연산자로

        (8) 스택에서 pop하고 왼쪽 피연산자로

        (9) 계산

        (10) 계산 결과를 스택에 push

(11) 마지막에 남은 값 한 개가 계산 결과

 

3. 후위 표기식 구현

• 15강 stackADT_array.c에 파일에 이어서 작성

//stackADT_array.c

...
//후위표기식 계산

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

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

//*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;
    }
}

//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 반환
}

//입력으로 하나의 연산자를 받아, 스택에서 pop을 2번한 연산결과를 리턴하는 함수
int eval_op(char op){
    //pop하기 전에 스택이 비었는지 확인
    //첫 번째 pop: right hand side: 오른쪽 피연산자
    if(is_empty(operand_stack))
        handle_exception("Syntax Error: Stack empty in eval_op");
    int rhs = pop(operand_stack);
    
    //두 번째 pop: left hand side: 왼쪽 피연산자
    if(is_empty(operand_stack))
        handle_exception("Syntax Error: Stack 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;
}

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

//stackADT_array.c

int main(){
    char expr[INIT_CAPACITY] = "7 4 - 3 * 1 5 + *";
    printf("%s ", expr);
    printf("= %d\\n", eval(expr));
}

//7 4 - 3 * 1 5 + * 
//= 54
// 7 4 - 3 * 1 5 + * = (7-4) * 3 * (1 + 5) = 54

 

 

 

 

---

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

https://www.youtube.com/watch?time_continue=1799&v=I-k8zRlaCbg&feature=emb_title