[9] 중위표기법(infix) to 후위표기법(postfix) _ 스택(stack)
우리가 일반적으로 수식을 표현하기 위해 나타내는 방법은
중위 표기법(infix)이다.
중위 표기법은 숫자와 같은 피연산자 사이에 덧셈, 곱하기 기호와 같은 이항 연산자가 위치하도록 하는 방식이다.
반면 컴파일러는 후위 표기법을 이용하여 계산을 수행한다.
후위 표기법(postfix)는 계산할 피연산자를 뒤에 이항 연산자가 위치하도록 하는 방식이다.
예를 들어
infix로 2 + 3*4 + 5/6 과 같은 식이 있다면
postfix로는 234 * + 56 / + 와 같이 나타낸다.
infix로 나타낸 수식을 postfix로 바꾸는 것은 어렵지 않다.
우선 계산 순서에 따라 괄호를 작성한다.
위의 2 + 3 * 4 + 5 / 6 을 예시로 들면,
( ( 2 + ( 3 * 4 ) ) + ( 5 / 6 ) ) 이렇게 괄호를 묶어줄 수 있다.
그런 다음 가장 안쪽에 있는 괄호부터 postfix로 나타내는데,
피연산자 먼저, 연산자를 뒤에 나타내면 된다.
다음 괄호에 대해서 같은 방법을 수행한다.
다음으로 가장 마지막 괄호에 대해서 동일하게 수행한다.
이를 프로그램으로 구현하고자 한다.
우선 연산자들을 저장하는 enumerated type의 precedence를 정의하면 다음과 같다.
|
1
|
typedef enum {lparen, rparen, plus, minus, times, divide, mod, eos, operand}precedence;
|
cs |
postfix로 나타내기 위해서 stack 자료구조를 이용한다.
스택을 이용할 때 linked list로 연결된 스택을 이용할 것이다.
따라서 다음과 같이 스택을 정의한다.
|
1
2
3
4
5
|
typedef struct _stack {
precedence data;
struct _stack* link;
}stack;
typedef stack *stackPointer;
|
cs |
스택에는 스택의 top의 연산자의 우선순위보다 큰 우선순위를 가질 때만 스택에 넣도록 한다.
단, 왼쪽 괄호가 있다면 오른쪽 괄호를 만날때까지 스택에 넣도록 한다.
예를 들어
a * ( b + c ) * d 라는 수식이 있으면 스택에는 다음과 같은 순서로 담긴다.
1. a
a 는 피연산자이므로 스택에 담기지 않고 바로 출력한다.
따라서 현재 출력은 a, 스택은 비어있는 상태이다.
2. *
* 는 연산자이므로 스택에 담는다.
따라서 현재 출력은 a, 스택에는 *가 담겨있는 상태이다.
3. (
( 는 * 보다 우선순위가 높으므로 스택에 담는다.
이때 오른쪽 괄호가 나올 때까지 모든 연산자를 스택에 담도록 한다.
따라서 현재 출력은 a, 스택은 다음과 같다.
4. b
b는 피 연산자 이므로 바로 출력한다.
따라서 현재 출력은 ab, 스택은 3과 동일하다.
5. +
+은 연산자이고, 아직 오른쪽 괄호가 없으므로 우선순위와 관계 없이 스택에 넣는다.
따라서 현재 출력은 ab이고, 스택은 다음과 같다.
6. c
c는 피연산자이므로 바로 출력하도록 한다.
따라서 현재 출력은 abc이고, 스택은 5와 동일하다.
7. )
왼쪽 괄호를 찾았으므로, 그동안 스택에 담긴 것을 모두 출력한다.
이때 당연히 괄호는 출력하지 않는다.
따라서 왼쪽 괄호를 만날때까지 pop 하면
현재 출력은 abc+ 이고 스택은 다음과 같다.
8. *
현재 top 은 * 인데 현재 문자도 * 이므로 우선순위가 같으므로,
현재 스택에 담긴 top을 출력하고 현재 문자를 push 한다.
따라서 출력 결과는 abc+* 이고 스택은 다음과 같다.
이전의 곱셈 연산자가 그대로 있는 것이 아니라 새로운 연산자가 들어온 것을 강조하기 위해 다른 색으로 표현하였다.
9. d
피연산자이므로 바로 출력한다.
따라서 현재 출력 결과는 abc+*d 이고 스택은 8과 동일하다.
10. eos ( 수식 끝 )
수식이 끝났으므로 스택에 남은 원소들을 모두 pop해서 출력하도록 한다.
따라서 최종 출력 결과는 abc+*d*이다.
위와 같은 과정을 C언어로 구현하였다.
C 언어 구현
앞에서 언급하였듯이 linked list로 구현된 스택을 이용하였으며,
연산자는 +, -, *, /, % 만 포함되고, 피연산자는 알파벳 문자 하나라고 가정하였다.
또한, input 파일은 "expr.txt"의 이름을 가지며,
input 파일의 예시는 같다.
|
1
|
(a - b / c) + d * e
|
cs |
따라서 input 파일을 입력받을 때 공백은 제외하고 입력을 받아야 한다.
출력 결과는 postfix 수식이며
출력 예시는 다음과 같다.
또한 메인 함수를 제외하고 선언된 함수는 다음과 같다.
1. void postfix()
스택에 담고 출력하는 일련의 과정을 수행하는 함수
2. precedence getToken(char*, int*)
input으로 받은 token이 어떤 기호(피연산자/수식 끝/연산자 등) 인지 precedence 로 리턴하는 함수
3. void rExpr(FILE*, char*)
txt 파일인 input 파일을 읽는 함수
4. void push(precedence)
스택에 push 하는 함수
5. precedence pop()
스택에서 pop 하는 함수
6. void printToken(precedence)
해당 token을 출력하는 함수
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
#include <stdio.h>
#include <stdlib.h>
#define MAX_EXPR_SIZE 100
typedef enum {lparen, rparen, plus, minus, times, divide, mod, eos, operand}precedence;
typedef struct _stack {
precedence data;
struct _stack* link;
}stack;
typedef stack *stackPointer;
char operator[] = { '(', ')', '+', '-', '*', '/', '%' };
char expr[MAX_EXPR_SIZE];
int isp[] = { 0, 19, 12, 12, 13, 13, 13, 0 };
int icp[] = { 20, 19, 12, 12, 13, 13, 13, 0 };
stack* top = NULL;
void postfix();
precedence getToken(char*, int*);
void rExpr(FILE*, char*);
void push(precedence);
precedence pop();
void printToken(precedence);
int main() {
FILE* fp;
fp = fopen("expr.txt", "r");
rExpr(fp, expr);
postfix();
system("pause");
return 0;
}
void postfix() {
char symbol;
precedence token;
int n = 0;
push(eos);
for (token = getToken(&symbol, &n); token != eos; token = getToken(&symbol, &n)) {
if (token == operand)
printf("%c", symbol);
else if (token == rparen) {
while (top->data != lparen)
printToken(pop());
pop();
}
else {
while (isp[top->data] >= icp[token])
printToken(pop());
push(token);
}
}
while ((token = pop()) != eos && top) {
printToken(token);
}
printf("\n");
}
precedence getToken(char* symbol, int*n) {
*symbol = expr[(*n)++];
if (*symbol == operator[0])
return lparen;
else if (*symbol == operator[1])
return rparen;
else if (*symbol == operator[2])
return plus;
else if (*symbol == operator[3])
return minus;
else if (*symbol == operator[4])
return times;
else if (*symbol == operator[5])
return divide;
else if (*symbol == operator[6])
return mod;
else if (*symbol == -1)
return eos;
else
return operand;
}
void rExpr(FILE* fp, char* expr) {
int i = 0;
char c;
if (!fp) {
fprintf(stderr, "Input file error\n");
exit(0);
}
do {
c= fgetc(fp);
if (c != ' ' ) {
expr[i] = c;
i++;
}
} while (c != EOF);
fclose(fp);
}
void push(precedence element) {
stackPointer temp;
temp = (stackPointer)malloc(sizeof(stack));
temp->data = element;
temp->link = top;
top = temp;
}
precedence pop() {
stackPointer temp = top;
precedence item;
if (!top) {
fprintf(stderr, "stack is empty\n");
exit(1);
}
item = temp->data;
top = temp->link;
free(temp);
return item;
}
void printToken(precedence symbol) {
printf("%c", operator[symbol]);
}
|
cs |
이는 O(n)의 시간 복잡도를 갖는다.