스택(stack)

스택(Stack)

• 자료(data element)를 보관할 수 있는 선형 구조
• 단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고(Push 연산)
• 꺼낼 때에는 같은 쪽에서 뽑아 꺼내야 하는 제약이 있음(Pop 연산)
• 후입선출(LIFO - Last In First Out) 특징을 가지는 선형 자료구조
• 스택 언더플로우(stack underflow) -  비어 있는 스택에서 데이터 원소를 꺼내려 할 때
• 스택 오버플로우(stack overflow) -  꽉 찬 스택에 데이터 원소를 넣으려 할 때

 

스택의 추상적 자료구조 구현

• 배열(array)를 이용하여 구현
  • python 리스트를 이용하여 구현

class ArrayStack:
    def __init__(self):
        self.data = []
        
    def size(self):
        return len(self.data)
    
    def imEmpty(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]

• 연결 리스트(linked list)를 이용하여 구현
  • 양방향 연결 리스트를 이용하여 구현

• 연산의 정의
  • size() - 현재 스택에 들어 있는 데이터 원소의 수를 구함
  • imEmpty() - 현재 스택이 비어 있는지를 판단
  • push(x) - 데이터 x를 스택에 추가
  • pop() - 스택의 맨 위에 저장된 데이터 원소를 제거(또한, 반환)
  • peek() - 스택의 맨 위에 저장된 데이터 원소를 반환(제거하지 않음)
• pythonds라는 라이브러리를 설치하면 Stack을 이용해 볼 수 있다.

 

연습문제 - 수식의 괄호 유효성 검사

• (A + B}
• ((A + B) + C)
• ((A + B) * (C + D))
• 접근:
  • 수식을 왼쪽부터 한글자씩 읽어서
  • 여는 괄호를 만나면 stack에 푸시
  • 닫는 괄호를 만나면 스택에서 pop. 이때 스택이 비어 있다면 올바르지 않은 수식
    • 스택에서 pop, 쌍을 이루는 여는 괄호인지 검사. 맞지 않다면 올바르지 않은 수식
  • 끝까지 검사한 후 스택이 비어있어야 올바른 수식

---

스택의 응용 - 수식의 후위 표기법

• 중위 표기법(infix notation) - 연산자가 피연사자들의 사이에 위치
• 후위 표기법(postfix notation) - 연산자가 피연산자들의 뒤에 위치

중위 표현식 -> 후위 표현식

• 피연산자는 그냥 적는다.
• 연산자는 스택에 삽입한다.
  • 다음에 또 연산자가 나왓을때 스택이 비어 있지 않다면,
  • 연산의 우선순위를 검토후 우선순위가 높은 연산자를 pop한후 피연사자 뒤에 적는다.
  • 연산자 낮은 연산자 다시 스택에 삽입
  • 만약 우선순위가 더 높은 연산자가 들어오는 경우에는 stack에 그냥 삽입하고 넘어간다.

알고리즘 설계

• 연산자의 우선순위 설정

prec = {
    '*':3, '/':3,
    '+':2, '-':2,
    '()': 1
}

• 중위표현식을 왼쪽부터 한글자씩 읽어서
  • 피연산자이면 그냥 출력
  • '('이면 스택에 push
  • ')'이면 '('이 나올때까지 스택에서 pop 출력
  • 연산자이면 스택에서 이보다 높거나 같은 우선순위 것들을 pop, 출력
    • 그리고 이 연산자는 스택에 push
  • 스택에 남아 있는 연산자는 모두 pop 출력
• 스택의 맨 위에 있는 연산자와의 우선순위 비교
  • 스택의 peek() 연산 이용
• 스택에 남아 있는 연산자 모두 pop() 하는 순환문
  • while not opStack.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
}

def solution(S):
    opStack = ArrayStack()
    answer = ''
    for s in S:
        if s == '(':
            opStack.push(s)
        else:
            if s.isalpha():
                answer += s
            elif s == ')':
                while opStack.peek() != '(':
                    answer += opStack.pop()
                opStack.pop()
            else:
                if opStack.isEmpty():
                    opStack.push(s)
                else:
                    while not opStack.isEmpty() and prec[opStack.peek()] >= prec[s]:
                        answer += opStack.pop()
                    opStack.push(s)
                    
    while not opStack.isEmpty():
        answer += opStack.pop()
    return answer

---

스택의 응용 - 후위 표기 수식 계산

알고리즘의 설계

• 후위 표현식을 왼쪽부터 한글자씩 읽어서
  • 피연산자를 만나면 스택에 push
  • 연산자를 만나면 스택에서 pop x 2번 연산한 후 이 결과를 스택에 push
• 스택의 끝에 도달하면 스택에서 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]


def splitTokens(exprStr):
    tokens = []
    val = 0
    valProcessing = False
    for c in exprStr:
        if c == ' ':
            continue
        if c in '0123456789':
            val = val * 10 + int(c)
            valProcessing = True
        else:
            if valProcessing:
                tokens.append(val)
                val = 0
            valProcessing = False
            tokens.append(c)
    if valProcessing:
        tokens.append(val)

    return tokens


def infixToPostfix(tokenList):
    prec = {
        '*': 3,
        '/': 3,
        '+': 2,
        '-': 2,
        '(': 1,
    }

    opStack = ArrayStack()
    postfixList = []
    
    for token in tokenList:
        if type(token) is int:
            postfixList.append(token)
        elif token == '(':
            opStack.push(token)
        elif token == ')':
            while opStack.peek() != '(':
                postfixList.append(opStack.pop())
            opStack.pop()
        else:
            if opStack.isEmpty():
                opStack.push(token)
            else:
                while not opStack.isEmpty() and prec[opStack.peek()] >= prec[token]:
                    postfixList.append(opStack.pop())
                opStack.push(token)
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())

    return postfixList


def postfixEval(tokenList):
    evalStack = ArrayStack()
    for token in tokenList:
        if type(token) is int:
            evalStack.push(token)
        elif token == '+':
            val_1 = evalStack.pop()
            val_2 = evalStack.pop()
            evalStack.push((val_2 + val_1))
        elif token == '-':
            val_1 = evalStack.pop()
            val_2 = evalStack.pop()
            evalStack.push((val_2 - val_1))
        elif token == '*':
            val_1 = evalStack.pop()
            val_2 = evalStack.pop()
            evalStack.push((val_2 * val_1))
        elif token == '/':
            val_1 = evalStack.pop()
            val_2 = evalStack.pop()
            evalStack.push((val_2 / val_1))
    return evalStack.pop()


def solution(expr):
    tokens = splitTokens(expr)
    postfix = infixToPostfix(tokens)
    val = postfixEval(postfix)
    return val