자료구조

후위표기식 전환 (스택이용) 1

Cycrypt0 2021. 6. 18. 21:19
728x90

Postfix1

정의 : 연산자를 피연산자 뒤에 표기하는 방법이다. Stack을 사용한 커퓨터의 계산을 위해서 고안된 계산법이며, 괄호가 필요 없다는 특징이 있다.

infix-> postfix :

infix로 표현된 수식

(a+b) * c / d + e




postfix로 표현된 수식

ab+c*d/e+




postfix 수식 계산

연산자를 만나면 앞선 두개의 피연산자들을 연산자로 계산한다.

i)a+bc*d/e+

ii)(a+b)*cd/e+

iii)(a+b)*(c/d)e+

iv)(a+b)*(c/d)+e





Stack에서 연산 방법

  1. 피연산자가 입력되면 Stack에 넣는다
  2. 연산자가 입력되면 Stack에서 피연산자 2개를 꺼내 계산 후 결과를 Stack에 넣는다.


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

typedef int element;        // 스택 원소(element)의 자료형을 int로 정의 

typedef struct  stackNode {    // 스택의 노드를 구조체로 정의
    element data;
    struct stackNode* link;
} stackNode;

stackNode* top;                // 스택의 top 노드를 지정하기 위해 포인터 top 선언

// 스택이 공백 상태인지 확인하는 연산
int isEmpty() {
    if (top == NULL) return 1;
    else return 0;
}

// 스택의 top에 원소를 삽입하는 연산
void push(element item) {
    stackNode* temp = (stackNode*)malloc(sizeof(stackNode));
    temp->data = item;
    temp->link = top;        // 삽입 노드를 top의 위에 연결
    top = temp;                // top 위치를 삽입 노드로 이동
}

// 스택의 top에서 원소를 삭제하는 연산
element pop() {
    element item;
    stackNode* temp = top;

    if (top == NULL) {        // 스택이 공백 리스트인 경우
        printf("\n\n Stack is empty !\n");
        return 0;
    }

    else {                    // 스택이 공백 리스트가 아닌 경우
        item = temp->data;
        top = temp->link;    // top 위치를 삭제 노드 아래로 이동
        free(temp);            // 삭제된 노드의 메모리 반환
        return item;        // 삭제된 원소 반환
    }
}

// 후위 표기법 수식을 계산하는 연산
element evalPostfix(char* exp) {
    int opr1, opr2, value, i = 0;
    // char형 포인터 매개변수로 받은 수식 exp의 길이를 계산하여 length 변수에 저장
    int length = strlen(exp);
    char symbol;
    top = NULL;
    for (int i = 0; i < length; i++) {
        switch (exp[i]) {
        case '+':
            opr2 = pop();    opr1 = pop();
            push(opr1 + opr2);    break;

        case '-':
            opr2 = pop();    opr1 = pop();
            push(opr1 - opr2);    break;

        case'*':
            opr2 = pop();    opr1 = pop();
            push(opr1 * opr2);    break;

        case'/':
            opr2 = pop();    opr1 = pop();
            push(opr1 / opr2);    break;

        default:
            value = exp[i] - '0';
            push(value);
            break;
        }
    }
    return pop();
}
// 수식 exp에 대한 처리를 마친 후 스택에 남아 있는 결과값을 pop하여 반환

void main(void) {
    int result;
    char* express = "35*62/-";
    printf("후위 표기식 : %s\n", express);

    result = evalPostfix(express);
    printf("\n\n연산 결과 => %d", result);

    getchar();
}

실행 결과

infix를 postfix로 변환하는 코드와 설명은 다음 포스트에서 설명할 예정이다.

728x90