알고리즘
후위 표기법
야식은진리다
2020. 8. 15. 12:26
수식을 표기하는 방법에는 우리가 흔히 사용하는 중위 표기법말고도 전위 표기법과 후위 표기법이라는 것이 있다.
중위 표기법 -> ( 1 + 2 ) * 7
후위 표기법 -> 1 2 + 7 *
전위 표기법 -> * + 1 2 7
이러한 전위, 후위 표기법의 특징은 연산자의 순서에 따라 연산순서가 결정되기 때문에 연산자 우선순위나 소괄호가 필요없다는 점이다.
중위 표기법을 후위 표기법으로 바꾸는 법
- 피연산자가 들어오면 바로 출력한다.
- 연산자가 들어오면 스택에 들어있는 연산자와 비교해서 스택에 있는 연산자보다 우선순위가 높으면 스택에 쌓고, 낮으면 스택에 있는 들어온 연산자보다 우선순위가 낮은 연산자를 모두 출력하고, 들어온 연산자를 스택에 쌓는다.
연산자 우선순위는
ㆍ *, / : 제일 높다
ㆍ +, - : 두번째로 높다
ㆍ ( : 가장 작다 - '('는 무조건 스택에 쌓는다.
- ')'를 만나면 '('를 만날 때까지 스택에서 출력한다. ( 소괄호는 제외 )
|
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
|
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "ListBaseStackCal.h"
int GetopPrec(char op)
{
switch (op)
{
case'*':
case'/':
return 4;
case'+':
case'-':
return 2;
case'(':
return 1;
}
return -1;
}
int WhoPrecOp(char op1, char op2)
{
int op1Prec = GetopPrec(op1);
int op2Prec = GetopPrec(op2);
if (op1Prec > op2Prec)
{
return 1;
}
else if (op1Prec < op2Prec)
{
return -1;
}
else return 0;
}
void ConvToRPNExp(char exp[])
{
Stack stack;
int expLen = strlen(exp);
char* convExp = (char*)malloc(expLen + 1);
int i, idx = 0;
char tok, popOp;
memset(convExp, 0, sizeof(char) * expLen + 1);
StackInit(&stack);
for (i = 0; i < expLen; i++)
{
tok = exp[i];
if (isdigit(tok)) convExp[idx++] = tok;
else
{
switch (tok)
{
case'(':
SPush(&stack, tok);
break;
case')':
while (1)
{
popOp = SPop(&stack);
if (popOp == '(')
break;
convExp[idx++] = popOp;
}
break;
case'+':case'-':
case'*':case'/':
while (!SIsEmpty(&stack)&&WhoPrecOp(SPeek(&stack),tok)>=0)
{
convExp[idx++] = SPop(&stack);
}
SPush(&stack, tok);
break;
}
}
}
while (!SIsEmpty(&stack))
{
convExp[idx++] = SPop(&stack);
}
strcpy(exp, convExp);
free(convExp);
}
|