12강: 스택의 응용 - 수식의 후위 표기법
후위 표기법(Postfix Notation)이란?
- 연산자를 두 피연산자의 뒤에 쓰는 방식
- 일상에서 사용하는 수식의 표기법은 중위 표기법(Infix Notation)
- 중위 표기법
(A + B) * (C + D)를 후위 표기법으로 변환
1
A B + C D + *
A + B * C를 변환한다면 ?
1
A B C * +
- 위처럼 후위 표기법을 이용한 연산을 할 때 스택이 이용된다
연산과정
A * B + C 를 후위 표현식으로 연산하는 과정
-
A는 피연산자이므로 적어준다 -
*는 연산자이기 때문에 스택에 집어넣는다 -
B는 피연산자이기 때문에 적는다 -
+는 연산자이고, 스택이 비어있지 않으므로 스택에 있는것과의 우선순위를 비교4-1. 비교한 후 높은 연산자가 스택에 있기 때문에(*) 스택에서 꺼내고
4-2. 낮은 연산자(+)는 비어있는 스택에 넣어준다
-
C는 피연산자이기 때문에 적는다 -
수식이 끝났기 때문에 스택에 있는 연산자를 꺼내서 적어준다
-
결과 :
A B * C +
A + B * C 를 후위 표현식으로 연산하는 과정
-
A는 피연산자이므로 적어준다 -
+는 연산자이기 때문에 스택에 넣어준다 -
B는 피연산자이므로 적어준다 -
*는 연산자이고, 스택이 비어있지 않으므로 스택에 있는것과의 우선순위를 비교4-1. 비교 후 높은 연산자(*)는 스택에 들어있지 않기 때문에 스택에 넣어준다
-
C는 피연산자이기 때문에 적어준다 -
수식이 끝났기 때문에 스택에 있는 연산자를 꺼내서 적어준다
-
결과 :
A B C * +
-
스택의 우선순위 비교
- 우선순위가 높은것을 스택에서 꺼내서 적어준다
- 만약 동일하다면 먼저들어온, 즉 스택에 있는 연산자를 꺼내서 적어준다
- 괄호가 있다면 괄호 우선순위를 가장 높게 !!
- 여는 괄호는 스택에 push
- 닫는 괄호를 만나면 여는 괄호가 나올 때 까지 pop 해주면 된다
- 단, 연산자를 만났을 때 여는괄호 너머까지 pop하지 않도록 여는괄호의 우선순위는 가장 낮게 설정해 주어야 한다
괄호가 있는 수식 A * (B + C) 를 후위 표기식으로 연산하는 과정
A는 피연산자 이므로 적어준다*는 연산자 이기 때문에 스택에 넣어준다((여는괄호)를 만났기 때문에 스택에 넣어준다+는 현재 스택에(가 있기 때문에 그 위에 넣어준다C는 피연산자 이므로 적어준다)(닫는괄호)를 만났기 때문에 현재 스택에서((여는괄호)를 만나기 전까지 연산자들을 꺼내 적어준다- 수식이 끝났기 때문에 스택에 남아있는 연산자를 꺼내준다
- 결과 :
A B C + *
괄호가 두개 있는 수식 (A + B) * (C + D) 를 후위 표기식으로 연산하는 과정
(를 스택에 넣어준다A는 피연산자 이므로 적어준다.+연산자는 현재 스택에(가 있기 때문에 그 위에 넣어준다B는 피연산자 이므로 적어준다.)를 만났기 때문에 스택에서(를 만날 때까지 스택에서 꺼내 적어준다*는 연산자이므로 스택에 넣어주는데, 스택이 비어있기 때문에 그대로 넣어준다(를 현재 스택의 위에 넣어준다C는 피연산자 이므로 적어준다+는 현재 스택에(가 있기 때문에 그 위에 넣어준다D는 피연산자 이므로 적어준다)를 만났기 때문에 스택에서(를 만날 때까지 스택에서 꺼내서 적어준다- 수식이 끝났기 때문에 스택에 남아있는 연산자를 꺼내준다
- 결과 :
A B + C D + *
- 다른 예제
(A + (B - C)) * D는 ?A B C - + D *
A * (B - (C + D))는?A B C D + - *
알고리즘의 설계
- 연산자의 우선순위 설정
1
2
3
4
5
prec = {
'*':3, '/':3,
'+':2, '-':2,
'(':1
}
- 중위 표현식을 왼쪽부터 한 글자씩 읽어서
- 피연산자이면 그냥 출력
(이면 스택에 push)이면(이 나올 때까지 스택에서 pop, 출력- 연산자이면 스택에서 이보다 높(거나 같)은 우선순위 것들을 pop, 출력
- 그리고 다 pop해서 출력한 후에는 지금 만난 연산은 스택에 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
'''
스택의 맨 위에 있는 연산자와의 우선순위 비교, 스택의 peek() 연산 이용
스택에 남아있는 연산자 모두 pop()하는 순환문 while not S.isEmpty(): 이용
'''
class ArrayStack:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def push(self, item):
self.data.append(item)
def pop(self):
return self.data.pop()
def peek(self):
return self.data[-1]
prec = {
'*': 3, '/': 3,
'+': 2, '-': 2,
'(': 1,
}
import string
def solution(S):
eng = string.ascii_lowercase
myStack = ArrayStack()
answer = ''
for i in S:
if(i in eng):
answer += i
else:
if(i == "("):
myStack.push(i)
elif(i == ")"):
item = None
while(not myStack.isEmpty()):
item = myStack.pop()
if(item == "("):
break
else:
answer += item
else:
if(not myStack.isEmpty()):
item = myStack.peek()
if(prec[item] >= prec[i]):
# 여기서 한번더 처리를 해주는 이유는
# 아래의 예외사항들을 처리해 주기 위해서
while(not myStack.isEmpty()):
item = myStack.pop()
answer += item
myStack.push(i)
else:
myStack.push(i)
else:
myStack.push(i)
while(not myStack.isEmpty()):
item = myStack.pop()
answer += item
return answer
1
2
3
4
5
6
7
8
# 예외사항
입력값 > A+B*C-D/E
기댓값 > ABC*+DE/-
실행한 결과값 > 'ABC*DE/-+'
입력값 > A+B*C-D
기댓값 > ABC*+D-
실행한 결과값 > 'ABC*D-+
본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니다.
