스택의 응용
수식의 후위 표기법
중위표기법(infix notation)
(a+b) * (c+d)
- 연산자가 피연산자들의 사이에 위치
후위표기법(postfix notation)
-연산자가 피연산자들의 뒤에 위치
ab+cd+* ==>괄호도 필요없어짐
중위표현식 -> 후위표현식으로 바꾸는걸 알고리즘 스택을 통해 표현해보기!
[중위] a*b+c
[후위]ab*c+
[중위]a+b*c
[후위]abc*+
여는 괄호는 스택에 push
닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop
연산자를 만났을때, 여는 괄호 너머까지 pop하지 않도록 여는 괄호의 우선순위는 가장 낮게 설정
알고리즘의 설계
1.연산자의 우선순위 설정
prec = {
'*':3, '/':3,
'+':2, '-':2,
'(':1
}
중위 표현식을 왼쪽부터 한글자씩 읽어서 피연산자면 그냥출력
'('이면 스택에 push
')'이면 '('이 나올때까지 스택에서 pop, 출력
연산자이면 스택에서 이보다 높(거나 같)은 우선순위 것들을 pop, 출력
그리고 이 연산자는 스택에 push
스택에 남아있는 연산자는 모두 pop, 출력
스택의 맨 위에있는 연산자와의 우선순위 비교
스택의 peek() 연산 이용
스택의 남아있는 연산자 모두 pop()하는 순환문
while not opStack.isEmpty():
