Data Structure/자료구조

[자료구조] 스택의 응용 - 후위 표기 수식의 계산

lumana 2024. 1. 15. 09:35

스택(Stack)의 응용 - 후위 표기 수식의 계산

수식

  • 수식은 연산자와 피연산자, 괄호로 이루어져 있음.

  • 연산자들은 우선순위가 있어 우선순위가 높은 연산자가 먼저 계산된다.

  • 컴퓨터는 스택을 이용하여 수식을 계산한다.

중위 / 후위 / 전위 표기 수식

  • 중위 표기 수식

    • 사람들이 일반적으로 수식을 표기하는 방식

    • 연산자가 피연산자 사이에 있으면 중위 표기 수식

  • 후위 표기 수식

    • 연산자가 피연산자 뒤에 있으면 후위 표기 수식

  • 전위 표기 수식

    • 연산자가 피연산자 앞에 있으면 전위 표기 수식

  • 예시

    • 2 + 3 * 4 (중위)

      • 234*+ // 후위 표기 수식

      • +2*34 // 전위 표기 수식

    • a * b + 5 (중위)

      • ab*5+ // 후위 표기 수식

      • +*ab5 // 전위 표기 수식

    • (1 + 2) * 7 (중위)

      • 12+7* // 후위 표기 수식

      • *+127 // 전위 표기 수식

  • 프로그래머가 수식을 중위 표기법으로 작성하면 컴파일러는 이것을 후위 표기법으로 변환한 후 스택을 이용하여 계산한다.

    • 중위 표기 방법에서는 면저 계산해야 할 부분을 나타내기 위해 괄호를 사용해야 하는데, 후위 표기 방법에서는 괄호가 필요 없기 때문

    • 연산자 우선순위를 고려할 필요가 없기 때문

    • 중위 표기 방법은 수식을 끝까지 읽은 후 계산을 시작하는 반면에, 후위 표기 방법을 사용하면 수식을 읽으면서 바로 계산할 수 있음

스택을 이용하여 후위 표기 수식을 계산하는 방법

  • 수식을 왼쪽에서 오른쪽으로 스캔

  • 피연산자이면 스택에 저장

  • 연산자이면 필요한 수 만큼의 피연산자를 스택에서 꺼내 연산을 수행하고 연산 결과를 스택에 저장

  • ex) 82/3-32*+ 계산

    • 8(피연산자)

    • 8 2(피연산자)

    • 4(연산자 '/'를 읽고 8 / 2를 계산한 후 스택에 저장)

    • 4 3(피연산자)

    • 1 (연산자 '-'를 읽고 4 - 3을 계산한 후 스택에 저장)

    • 1 3(피연산자)

    • 1 3 2 (피연산자)

    • 1 6 (연산자 '*'를 읽고 3 * 2를 계산한 후 스택에 저장)

    • 7 (연산자 '+'를 읽고 1 + 6을 계산한 후 스택에 저장)

  • 만약 연산을 하려고 하는데 스택에 원하는 만큼의 피연산자가 없으면 오류가 된다

  • 의사 코드

    calc_posfix:
  스택 s를 생성하고 초기화
  for item in 후위표기식 do
    if (item == 피연산자)
      push(s, item)
    else if (item == 연산자(op) 이면)
      second <- pop(s)
      first <- pop(s)
      result <- first op second // op는 +-*/ 중 하나
      push(s, result)
  final_result <- pop(s);

  • C Program

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100

typedef char element;  // 교체!
                      // 차후에 스택이 필요하면 여기만 복사하여 붙인다.
                      // ===== 스택 코드의 시작 =====
#define MAX_STACK_SIZE 100

typedef struct {
    element data[MAX_STACK_SIZE];
    int top;
} StackType;

// 스택 초기화 함수
void init_stack(StackType *s) {
    s->top = -1;
}

// 공백 상태 검출 함수
int is_empty(StackType *s) {
    return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s) {
    return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType *s, element item) {
    if (is_full(s)) {
        fprintf(stderr, "스택 포화 에러\n");
        return;
    } else
        s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    } else
        return s->data[(s->top)--];
}
// 피크함수
element peek(StackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    } else
        return s->data[s->top];
}
// ===== 스택 코드의 끝 =====

// 후위 표기 수식 계산 함수
int eval(char exp[]) {
    StackType s;
    char item;
    int op, first, second, value, i = 0;
    int result, len = strlen(exp);  // n은 수식의 길이
    init_stack(&s);
    for (i = 0; i < len; i++) {
        item = exp[i];
        if (item != '+' && item != '-' && item != '*' && item != '/') {  // 피연산자면
            value = item - '0';
            push(&s, value);
        } else {  // 연산자이면 피연산자를 스택에서 꺼낸다
            second = pop(&s);
            first = pop(&s);
            switch (item) {  // 연산을 수행하고 스택에 저장
                case '+':
                    push(&s, first + second);
                    break;
                case '-':
                    push(&s, first - second);
                    break;
                case '*':
                    push(&s, first * second);
                    break;
                case '/':
                    push(&s, first / second);
                    break;
            }
        }
    }
    return pop(&s);
}

int main(void) {
    int result;
    printf("후위표기식은 82/3-32*+\n");
    result = eval("82/3-32*+");
    printf("결과값은 %d\n", result);
    return 0;
}

중위 표기 수식을 후위 표기 수식으로 변환

  • 프로그래머가 입력한 중위 표기 수식을 컴파일러가 계산하려면 후위 표기 수식으로 변경하는 것이 필요

    • 중위 표기법과 후위 표기법의 공통점은 피연산자의 순서는 동일하다는 점

    • 연산자들의 순서는 다름

    • 연산자들의 순서는 우선순위에 다라 결정됨

  • 중위 표기 수식을 후위 표기 수식으로 변환하는 과정

    • 왼쪽에서 오른쪽으로 스캔

    • 피연산자를 만나면 바로 후위 표기 수식에 출력

    • 연산자를 만나면 어딘가에 잠시 저장함

      • 후위 표기 수식에서는 기본적으로 피연산자들 뒤에 연산자가 나오기 때문

      • 따라서 출력할 적절한 위치를 찾을 때 까지 출력을 보류함

    • a + b *c의 경우 a, b, c는 그대로 출력되지만, + 와 * 중 어떤 것이 먼저 출력되어야 하는지 결정해야 함

      • 기본적으로 가장 나중에 스캔된 연산자가 가장 먼저 출력되어야 한다.

      • 따라서 연산자를 스택에 저장(후입 선출)

      • a

      • a | +

      • a b | +

      • a b | + *

      • a b c | + *

      • a b c *+ // 가장 나중에 스캔된 연산자가 가장 먼저 출력되어야 함

    • 문제점) a * b + c의 경우 *가 스택에 들어가 있는 상태에서 +를 넣으면 + 가 * 보다 먼저 계산되는 문제가 발생

      • 따라서 스택에 존재하는 연산자가 현재 처리중인 연산자보다 우선순위가 높으면 일단 스택에 있는 연산자들 중에서 우선순위가 높은 연산자를 먼저 출력한 다음에 처리중인 연산자를 스택에 넣어야 함

      • 우선순위가 같은 경우에도 일단 스택 상단의 요소를 꺼내어 출력해야 한다

      • a

      • a | *

      • a b | *

      • a b * | +

      • a b * c | +

      • a b * c +

    • 괄호를 처리하는 과정 ex) (a + b) * c

      • 왼쪽 괄호는 무조건 스택에 삽입 (왼쪽 괄호를 가장 우선순위가 낮은 연산자로 취급)

      • 따라서 다음에 만나는 어떤 연산자도 스택에 삽입

      • 오른쪽 괄호를 만나게 되면 왼쪽괄호가 삭제될 때 까지 왼쪽 괄호위에 쌓여있는 연산자들을 출력한다

      • | (

      • a | (

      • a | ( +

      • a b | ( +

      • a b + |

      • a b + | *

      • a b + c | *

      • a b + c *

  • 의사 코드

    infix_to_postfix(exp):

스택 s를 생성하고 초기화
while (exp에 처리할 문자가 남아 있으면)
  ch <- 다음에 처리할 문자
  switch(ch) 
  case 연산자:
    while (peek(s)의 우선순위 >= ch의 우선순위) do
      e <- pop(s)
      e를 출력
    push(s, ch);
    break;
  case 왼쪽 괄호:
    push(s, ch);
    break;
  case 오른쪽 괄호:
    e <- pop(s)
    while (e != 왼쪽 괄호) do
      e를 출력
      e <- pop(s)
    break;
  case 피연산자:
    ch를 출력
    break;
while (not is_empty(s)) do
  e <- pop(s)
  e를 출력

  • C Program

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100

typedef char element;        // 교체!
              // 차후에 스택이 필요하면 여기만 복사하여 붙인다. 
              // ===== 스택 코드의 시작 ===== 
#define MAX_STACK_SIZE 100

typedef struct {
  element data[MAX_STACK_SIZE];
  int top;
} StackType;

// 스택 초기화 함수
void init_stack(StackType *s)
{
  s->top = -1;
}

// 공백 상태 검출 함수
int is_empty(StackType *s)
{
  return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s)
{
  return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType *s, element item)
{
  if (is_full(s)) {
    fprintf(stderr, "스택 포화 에러\n");
    return;
  }
  else s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType *s)
{
  if (is_empty(s)) {
    fprintf(stderr, "스택 공백 에러\n");
    exit(1);
  }
  else return s->data[(s->top)--];
}
// 피크함수
element peek(StackType *s)
{
  if (is_empty(s)) {
    fprintf(stderr, "스택 공백 에러\n");
    exit(1);
  }
  else return s->data[s->top];
}
// ===== 스택 코드의 끝 ===== 

// 연산자의 우선순위를 반환한다.
int prec(char op) {
    switch(op) {
        case '(' : case ')' : return 0;
        case '+' : case '-' : return 1;
        case '*' : case '/' : return 2;
    }
    return -1;
}

// 중위 표기 수식 -> 후위 표기 수식
void infix_to_postfix(char exp[]) {
    StackType s;
    char ch, top;
    int i, len = strlen(exp);
    init_stack(&s);
    for (i = 0; i < len; i++) {
        ch = exp[i];
        switch (ch) {
            case '+' : case '-' : case '*' : case '/' : // 연산자
                while(!is_empty(&s) && (prec(peek(&s)) >= prec(ch))) {
                    printf("%c", pop(&s));
                }
                push(&s, ch);
                break;
            case '(' : // 왼쪽 괄호
                push(&s, ch);
                break;
            case ')' : // 오른쪽 괄호
                top = pop(&s);
                while (top != '(') {
                    printf("%c",  top);
                    top = pop(&s);
                }
                break;
            default : // 피연산자
                printf("%c", ch);
                break;
        }
    }
    while (!is_empty(&s)) {
        printf("%c", pop(&s));
    }
}

int main(void) {
  char *s = "(2+3)*4+9";
  printf("중위표시수식 %s \n", s);
  printf("후위표시수식 ");
  infix_to_postfix(s);
  printf("\n");
  return 0;
}

참조) C언어로 쉽게 풀어 쓴 자료구조(천인국, 2016, 생능출판사)

'Data Structure > 자료구조' 카테고리의 다른 글

[자료구조] 단순 연결 리스트 구현  (0) 2024.03.26
[자료구조] 스택의 응용 - 미로 탐색  (0) 2024.01.15
[자료구조] 스택의 응용 - 괄호 검사 문제  (0) 2024.01.15
[자료구조] 스택(Stack)  (0) 2023.12.31
[자료구조] 배열의 응용 : 희소행렬  (0) 2023.12.26

'Data Structure/자료구조'의 다른글

  • 현재글[자료구조] 스택의 응용 - 후위 표기 수식의 계산

관련글

티스토리툴바