스택(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.03.26 |
| [자료구조] 이중 연결 리스트(Doubly Linked List) 구현 (0) | 2024.03.26 |
| [자료구조] 단순 연결 리스트 구현 (0) | 2024.03.26 |
| [자료구조] 스택의 응용 - 미로 탐색 (0) | 2024.01.15 |