[자료구조] 스택을 이용한 중위표기식 > 후위표기식 변경 및 후위표기식 표현방법

스택을 이용하여, 중위표기식을 후위표기식으로 변경하기 위한 절차는 다음과 같다.

 

1. 스택 및 연산자 우선순위 함수 정의:
   • 스택을 위한 구조체 및 스택 관련 함수들을 정의한다. (createStack, isEmpty, peek, push, pop)
   • 연산자의 우선순위를 반환하는 함수인 getPrecedence를 정의한다.
2. 중위 표기식을 후위 표기식으로 변환하는 함수 정의 (infixToPostfix):
   • 입력된 중위 표기식을 문자열로 받아오고, 후위 표기식을 저장할 문자열(postfix)을 초기화한다.
   • 반복문을 통해 중위 표기식을 한 글자씩 읽으면서 처리한다.
   • 피연산자일 경우, 그대로 후위 표기식에 추가한다.
   • 여는 괄호일 경우, 스택에 push한다.
   • 닫는 괄호일 경우, 여는 괄호를 만날 때까지 스택에서 연산자를 pop하고 후위 표기식에 추가한다. 여는 괄호를 스택에서도 pop한다.
   • 연산자일 경우, 스택의 연산자보다 우선순위가 높거나 같을 때까지 스택에서 pop하고 후위 표기식에 추가한 뒤, 현재 연산자를 스택에 push한다.
3. 남은 연산자 처리:
   • 중위 표기식을 모두 처리한 후, 스택에 남아있는 모든 연산자를 pop하고 후위 표기식에 추가한다.
4. 메인 함수 (main):
   • 사용자로부터 중위 표기식을 입력 받는다.
   • infixToPostfix 함수를 호출하여 중위 표기식을 후위 표기식으로 변환한다.
   • 후위 표기식을 출력한다.

 

 

[관련 코드- c language]

 

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

// 스택 구조체 정의
typedef struct {
    char* array;
    int top;
    unsigned capacity;
} Stack;

// 스택 관련 함수들
Stack* createStack(unsigned capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (char*)malloc(stack->capacity * sizeof(char));
    return stack;
}

int isEmpty(Stack* stack) {
    return stack->top == -1;
}

char peek(Stack* stack) {
    return stack->array[stack->top];
}

void push(Stack* stack, char op) {
    stack->array[++stack->top] = op;
}

char pop(Stack* stack) {
    if (!isEmpty(stack))
        return stack->array[stack->top--];
    return '$'; // 스택이 비어있을 때 반환할 임의의 값
}

// 연산자의 우선순위를 반환하는 함수
int getPrecedence(char op) {
    switch (op) {
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    case '^':
        return 3;
    }
    return -1; // 연산자가 아닌 경우
}

// 중위 표기식을 후위 표기식으로 변환하는 함수
void infixToPostfix(char* infix, char* postfix) {
    Stack* stack = createStack(strlen(infix));
    int i, j;
    for (i = 0, j = -1; infix[i]; ++i) {
        // 피연산자는 바로 출력
        if (isalnum(infix[i]))
            postfix[++j] = infix[i];
        // 여는 괄호는 스택에 push
        else if (infix[i] == '(')
            push(stack, infix[i]);
        // 닫는 괄호를 만날 때까지 스택에서 연산자를 pop하고 출력
        else if (infix[i] == ')') {
            while (!isEmpty(stack) && peek(stack) != '(')
                postfix[++j] = pop(stack);
            if (!isEmpty(stack) && peek(stack) != '(')
                return; // 괄호 짝이 맞지 않음
            else
                pop(stack); // 여는 괄호를 스택에서 제거
        }
        // 연산자일 경우, 스택의 연산자보다 우선순위가 높거나 같은 동안 pop하고 출력
        else {
            while (!isEmpty(stack) && getPrecedence(infix[i]) <= getPrecedence(peek(stack)))
                postfix[++j] = pop(stack);
            push(stack, infix[i]);
        }
    }

    // 남은 연산자를 출력
    while (!isEmpty(stack))
        postfix[++j] = pop(stack);

    postfix[++j] = '\0';
}

int main() {
    char infix[100], postfix[100];
    
    // 중위 표기식 입력 받기
    printf("중위 표기식을 입력하세요: ");
    scanf("%s", infix);

    // 중위 표기식을 후위 표기식으로 변환
    infixToPostfix(infix, postfix);

    // 후위 표기식 출력
    printf("후위 표기식: %s\n", postfix);