중위 -> 후위는
스택에 연산자를 넣는다.
연산자인 경우 while문으로 비교하며 돌린다.
while (!is_empty(&s) && (prec(ch) <= prec(peek(&s))))
'('은 바로 스택에 push한다.
')'을 만나면 스택의 '('을 만날 때까지 pop 해준다.
그리고 '('은 후위표기식에 들어가지 않는다.
후위 표기식 계산은
스택에 피연산자를 넣는다.
연산자를 만나면
스택에서 피연산자 두 개 뽑아서 계산하면 끝
|
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char element;
#define MAX_STACK_SIZE 100
typedef struct {
element data[MAX_STACK_SIZE];
int top;
} StackType;
// 스택 초기화 함수
void init_stack(StackType* s) {
// 스택은 -1로 초기화
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;
}
// 중위 표기 수식 -> 후위 표기 수식
// stack에 연산자 넣는다
char* infix_to_postfix(const char exp[])
{
int i = 0;
char ch, top_op;
int len = strlen(exp);
StackType s;
char* postfix = (char*)malloc(len + 1); // 후위 표기식을 저장할 배열을 할당
// 후위 표기 배열 저장 인덱스
int pos = 0;
init_stack(&s); // 스택 초기화
for (i = 0; i < len; i++) {
ch = exp[i];
switch (ch) {
case '+': case '-': case '*': case '/': // 연산자
// 스택에 있는 연산자의 우선순위가 더 크거나 같으면 pop
while (!is_empty(&s) && (prec(ch) <= prec(peek(&s))))
postfix[pos++] = pop(&s);
push(&s, ch);
break;
// 괄호는 그냥 push
case '(': // 왼쪽 괄호
push(&s, ch);
break;
case ')': // 오른쪽 괄호
top_op = pop(&s);
// 왼쪽 괄호를 만날때까지 출력
while (top_op != '(') {
postfix[pos++] = top_op;
top_op = pop(&s);
}
break;
default: // 피연산자는 바로 넣는다
postfix[pos++] = ch;
break;
}
}
while (!is_empty(&s)) // 스택에 저장된 남아있는 연산자들 출력
postfix[pos++] = pop(&s);
// NULL 문자 추가
postfix[pos] = '\0';
return postfix;
}
// 후위 표기 수식 계산 함수
// stack에 숫자 넣는다
int eval(char exp[])
{
int op1, op2, value, i = 0;
int len = strlen(exp);
char ch;
StackType s;
init_stack(&s);
for (i = 0; i < len; i++) {
ch = exp[i];
if (ch >= '0' && ch <= '9') { // 피연산자(숫자)
value = ch - '0'; // 문자 '0'을 빼서 실제 정수값으로 변환
// 스택에 넣는다
push(&s, value);
}
else { // 연산자일 경우
// 피연산자 두 개를 뺀다
op2 = pop(&s); // 두 번째 피연산자를 먼저 pop
op1 = pop(&s); // 첫 번째 피연산자를 나중에 pop
switch (ch) {
case '+': push(&s, op1 + op2); break;
case '-': push(&s, op1 - op2); break;
case '*': push(&s, op1 * op2); break;
case '/': push(&s, op1 / op2); break;
}
}
}
return pop(&s); // 스택에 남아 있는 최종 결과 반환
}
int main(void)
{
const char* s = "(2+3)*4+9";
printf("중위표시수식 %s \n", s);
printf("후위표시수식 ");
char* tmp = infix_to_postfix(s);
printf("%s\n", tmp);
printf("결과값: ");
printf("%d", eval(tmp));
return 0;
}
|
cs |