스택 & 후위 연산자
스택
자료를 보관할 수 있는 선형 구조를 말한다. 단, 넣을 때 같은 입구에 밀어 넣어야하고, 꺼낼 때에도 같은 입구로 뽑아 꺼내야하는 제약이 있다. (밀어 넣다 → push, 뽑아 올리다 → pop)
컴퓨터 내부에서 프로그램이 실행할 때 함수 호출이 일어나고 함수들이 리턴하면 마지막 호출된 곳으로 돌아가는 동작을 구현하는 데에도 스택을 사용한다.
"재귀 함수" 가 줄줄이 호출되었다가 줄줄이 리턴하는 모습
- 호출 시: 함수가 호출되면 현재 함수의 상태가 스택에 푸시(push)된다.
- 리턴 시: 함수가 리턴되면 스택에서 해당 함수의 상태가 팝(pop)되고, 이전에 호출된 함수로 돌아간다.
1. 호출: factorial(4)
[ factorial(4) ]
2. 호출: factorial(3)
[ factorial(4), factorial(3) ]
3. 호출: factorial(2)
[ factorial(4), factorial(3), factorial(2) ]
4. 호출: factorial(1)
[ factorial(4), factorial(3), factorial(2), factorial(1) ]
5. 리턴: factorial(1) 종료 (리턴 값 1)
[ factorial(4), factorial(3), factorial(2) ]
6. 리턴: factorial(2) 종료 (리턴 값 2)
[ factorial(4), factorial(3) ]
7. 리턴: factorial(3) 종료 (리턴 값 6)
[ factorial(4) ]
8. 리턴: factorial(4) 종료 (리턴 값 24)
[ ]
스택에서 발생하는 오류
- 비어 있는 스택에서 원소를 꺼낼 경우 (stack underflow)
2. 꽉 찬 스택에 원소를 넣으려 할 경우 (stack overflow)
스택의 응용 - 수식의 후위 표기법 (Postfix Notation)
중위 표기법
(A + B) * (C + D)
- 연산자가 피연산자 사이에 위치한다. (우리가 쉽게 알고 있는 사칙연산 표기법)
후위 표기법
A B C * +
- 연산자가 피연산자들의 뒤에 위치한다.
그저 전공강의나 정보처리기사에서 기계적으로 배웠덨던 후위 표기 방식의 필요성이 궁금해지게 되었다.
후위 표기법을 사용하는 이유는?
- 괄호가 필요 없다. 괄호를 쓰지 않고도 우선 계산하여야 할 내용을 나타낼 수 있다. 이는 2번째 이유의 연장선이라고 생각한다. 괄호는 순위를 의미하니까.
- 괄호에 의한 연산자의 우선 순위도 생각할 필요가 없다. 식 자체에서 우선순위가 표현되어 있기 때문이다.
- 수식을 읽으면서 바로 계산할 수 있다. 중위 표현식의 경우, 괄호가 존재하므로 수식을 끝까지 읽은 후에 계산을 시작해야하는데 후위 표현식은 스택을 이용하여 바로 계산한다.
- 따라서 정리하면, 컴퓨터로 계산할 경우, 우선순위를 정하지 않고 계산할 수 있어 계산의 효율성을 얻을 수 있다는 장점이 존재한다는 것이다. 또한 수식을 읽으면서 바로 계산할 수 있다는 점에서 스택을 이용할 수 있기에 스택을 사용한 후위 표기법에 대해 배운다고 할 수 있다.
중위 표기법 -> 후위 표기법 변환 과정
- 중위 표기법을 왼쪽 부터 스캔한다.
- 피연산자는 출력한다.
- 연산자는 stack에 push한다.
- 다시 한번 연산자일 경우 안에 있는 stack의 값과 우선 순위를 비교하여 push 또는 pop한다.top이 새로 들어온 값(w)보다 우선순위가 작으면 push()한다.
이 경우 한번만 비교하는 것이 아니라 pop을 했더라도 반복문을 통해 스택의 top(peek)의 값과 우선순위를 계속해서 비교해야한다. - top이 새로 들어온 값(w)보다 우선순위가 크면 pop()
- 더이상 피연산자가 존재하지 않을 경우 stack에서 모두 pop한다.
괄호의 처리
(A+B)*C → stack(["(” , ”+” , “)” )]) → stack([(”*”)])
기본 설계 : 닫는 괄호( “)” )를 만나면 여는 괄호( “(” )가 나올때까지 pop한다.
- 괄호가 뒤에 위치한 경우.
A * (B+C)
우선 순위와 관련 없이 괄호를 stack안 에 넣는다. 단, 괄호 이전 연산을 pop 하지 않도록 여는 괄호의 우선순위를 낮게 부여한다.
실습
중위연산자를 후위연산자로 변환하기
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
}
def solution(S):
opStack = ArrayStack()
answer = ''
for w in S:
# 피연산자 및 괄호인지 확인
if(w not in prec):
if(w != ")"):
answer += w
# "("는 바로 스택에 넣는다
if(w == "("):
onStack.push(w)
continue
else:
# peek()를 이용하기 위해서 size 확인
if(opStack.size() == 0 ):
opStack.push(w)
continue
# 반복문을 활용한 우선순위 비교
for _ in range(opStack.size()):
if(prec[opStack.peek()] >= prec[w]):
if(w != "("):
pop_w = opStack.pop()
answer += pop_w
opStack.push(w)
# 닫는 괄호인 경우, 여는 괄호를 만날 때까지 pop
if(w == ")"):
for _ in range(opStack.size()):
pop_w = opStack.pop()
if(pop_w != "("):
answer += pop_w
else :
break
# 피연산자 출력이 끝난 뒤 후위 연산
if(opStack.size() != 0):
for _ in range(opStack.size()):
pop_w = opStack.pop()
answer += pop_w
print(answer)
return answer내가 가장 간과했던 부분은 아래와 같다.
# 반복문을 활용한 우선순위 비교
for _ in range(opStack.size()):
if(prec[opStack.peek()] >= prec[w]):
if(w != "("):
pop_w = opStack.pop()
answer += pop_w
opStack.push(w)
우선 순위 비교는 if문을 통해 한번만 이루어져선 안되고 지속적으로 스택의 top값과 비교했어야했는데, 테스트 케이스는 전부 통과하다 보니 위 부분이 부족하다는 사실을 인지하지 못했다.
ABC*-+” 테스트 케이스 추가
후에 A + B * C - D와 같은 테스트 케이스를 추가해보았는데, 반복문을 활용하지 않으면 “ABC*-+”가 된다. 하지만 후위연산자는 왼쪽에서부터 출력이 진행되고, 스택을 활용하게 되면 “+”와 “-”가 우선순위 값이 같기 때문에 “ABC*+-”가 되어야한다는 것을 알게 되었다.
우선순위가 같을 경우, 스택에 일찍 넣은 순서 정렬해서 pop하는 방법을 고민하다가 애초에 반복문을 이용하여 우선순위를 비교하면 출력 시 다시 순서를 재정렬 할 필요가 없다는 것을 알게되었다.