스택 & 후위 연산자

스택

자료를 보관할 수 있는 선형 구조를 말한다. 단, 넣을 때 같은 입구에 밀어 넣어야하고, 꺼낼 때에도 같은 입구로 뽑아 꺼내야하는 제약이 있다. (밀어 넣다 → 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)
   [ ]

스택에서 발생하는 오류

  1. 비어 있는 스택에서 원소를 꺼낼 경우 (stack underflow)

 

    2. 꽉 찬 스택에 원소를 넣으려 할 경우 (stack overflow)

스택의 응용 - 수식의 후위 표기법 (Postfix Notation)

중위 표기법

(A + B) * (C + D)
  • 연산자가 피연산자 사이에 위치한다. (우리가 쉽게 알고 있는 사칙연산 표기법)

후위 표기법

A B C * +
  • 연산자가 피연산자들의 뒤에 위치한다.

그저 전공강의나 정보처리기사에서 기계적으로 배웠덨던 후위 표기 방식의 필요성이 궁금해지게 되었다.

후위 표기법을 사용하는 이유는?

  1. 괄호가 필요 없다. 괄호를 쓰지 않고도 우선 계산하여야 할 내용을 나타낼 수 있다. 이는 2번째 이유의 연장선이라고 생각한다. 괄호는 순위를 의미하니까.
  2. 괄호에 의한 연산자의 우선 순위도 생각할 필요가 없다. 식 자체에서 우선순위가 표현되어 있기 때문이다.
  3. 수식을 읽으면서 바로 계산할 수 있다. 중위 표현식의 경우, 괄호가 존재하므로 수식을 끝까지 읽은 후에 계산을 시작해야하는데 후위 표현식은 스택을 이용하여 바로 계산한다.
  • 따라서 정리하면, 컴퓨터로 계산할 경우, 우선순위를 정하지 않고 계산할 수 있어 계산의 효율성을 얻을 수 있다는 장점이 존재한다는 것이다. 또한 수식을 읽으면서 바로 계산할 수 있다는 점에서 스택을 이용할 수 있기에 스택을 사용한 후위 표기법에 대해 배운다고 할 수 있다.

중위 표기법 -> 후위 표기법 변환 과정

 

  1. 중위 표기법을 왼쪽 부터 스캔한다.
  2. 피연산자는 출력한다.
  3. 연산자는 stack에 push한다.
  4. 다시 한번 연산자일 경우 안에 있는 stack의 값과 우선 순위를 비교하여 push 또는 pop한다.top이 새로 들어온 값(w)보다 우선순위가 작으면 push()한다. 
    이 경우 한번만 비교하는 것이 아니라 pop을 했더라도 반복문을 통해 스택의 top(peek)의 값과 우선순위를 계속해서 비교해야한다.
  5. top이 새로 들어온 값(w)보다 우선순위가 크면 pop()
  6. 더이상 피연산자가 존재하지 않을 경우 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하는 방법을 고민하다가 애초에 반복문을 이용하여 우선순위를 비교하면 출력 시 다시 순서를 재정렬 할 필요가 없다는 것을 알게되었다.

 

저작자표시 비영리

티스토리툴바