[Stack] python으로 구현한 자료구조 stack

stack

Stack은 LIFO 규칙을 따르는 자료구조로 데이터를 삽입할 때는 마지막 위치에 들어오고 데이터를 삭제 & 반환할때도 마지막 위치부터 삭제 & 반환을 하는 알고리즘이다.

스택의 경우는 활용범위가 넓기 때문에 잘 알고 있다면 유용하게 사용 할 수 있다. 그리고 특히 알고리즘 문제나 기업 코딩 테스트에도 빈번하게 나오기 때문에 로직을 잘 이해하고 다양한 스택 관련 문제를 풀면 좋다.

 

 

코드구현

class ArrayStack:
		'''
		By using python list make stack
		'''

    def __intit__(self):
        self.data = []
    
    def is_Empty(self):
        return True if not self.data else False

    def size(self):
        return len(self.data)

    def push(self, item):
        return self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]

    

class LinkedListStack:
		'''
		By using DoubleLinkedList make stack
		'''
    
    def __init__(self):
        self.data = DoublyLinkedList()

    def size(self):
        return self.data.getLenth()

    def is_Empty(self):
        return True if not self.data.getLength() else False

    def size(self):
        return self.data.getLenth()

    def push(self, item):
        node = Node(item)
        self.data.insertAt(self.data.size() + 1,  node)

    def pop(self):
        return self.data.popAt(self.data.size())

    def peek(self):
        return self.data.getAt(self.data.size()).data

Stack 자료구조의 경우 파이썬의 리스트와 양뱡형 연결 리스트를 이용해서 구현을 하면 구현자체는 어렵지 않다. 하지만 스택이 가진 특징을 정확히 이해하고 다양한 문제에 활용하는 것이 중요하다.

 

중위 표현식과 후위 표현식

대표적인 stack의 예제로 중위 표기법을 후위 표기법으로 변환시키는 문제가 있다.

본격적인 예제를 들여보기전 중위 표기법과 후위 표기법에 대하 간략하게 살펴보자.

1. 중위 표기법(infix notation)

• 연산자가 피연산자들 사이의 위치

2. 후외 표기법(postfix notation)

• 연산자가 피연산자들 뒤에 위치

ex)
A + B * C - 중위 == ABC * + - 후위
A * B + C == AB * C
A + B + C == AB+C+
(A + B) * C == AB + C *
A * (B + C) == ABC +*

-> 연산자 우선순위에 맞게 위치

 

설계

중위 표현식 -> 후위 표현식 알고리즘 설계(if 중첩으로 모든게 설명이 된다)

1) 피연산자이면 그냥 출력

2) '('이면 스택에 push

3) ')' 이면 '('이 나올때 까지 스택에서 pop, 출력

4) 연산자이면 스택에서 이보다 높(거나 같)은 우선순위 것들을 pop, 출력 그리고 이 연산자는 스택에 push

5) 스택에 남아 있는 연산자는 모두 pop, 출력.

 

코드 구현 1.(입력값이 공백이 없다고 가정 + 알파벳)

 

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

def conver_pre(s):
    stack = []
    re = ''
    for c in s:
        if c not in '()+-*/':
            re += c
        elif c == '(':
            stack.append(c)
        elif c == ')':
            while stack[-1] != '(':
                re += stack.pop()
            stack.pop()
        elif stack and prec_n[c] <= prec_n[stack[-1]]:
            re += stack.pop()
            stack.append(c)
        else:
            stack.append(c)
                
    while stack:
        re += stack.pop()
    return re



if __name__ == "__main__":
    # test cases
    print(conver_pre('(A+B)*C'))
    print(conver_pre('a+b+c'))
    print(conver_pre('a+b*c'))
    print(conver_pre('a*b-c'))
    print(conver_pre('(A+B*C)+D'))
    print(conver_pre('(A*B-C)-D'))
    print(conver_pre('(A*B)-(D*E+F)'))

코드 구현 2.(입력값 숫자)

# infixToPostfix.py

def splitTokens(expStr):
    tokens = []
    val = 0
    valProcessing = False
    for c in expStr:
        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


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


def infixToPostfix(s):
    re = ''
    stack = []
    for c in s:
        if type(c) is int:
            re += str(c)
        else:
            if not stack and c in '*/-+(':
                stack.append(c)
            elif c == "(":
                stack.append(c)
            elif stack and c == ")":
                while stack[-1] != "(":
                    re += stack.pop()
                stack.pop()
            elif prec.get(c) <= prec.get(stack[-1]):
                re += stack.pop()
                stack.append(c)
            else:
                stack.append(c)
    while stack:
        re += stack.pop()
    return re


def test():
    result = []
    test_case = ['1+2 * (3+1)', '1+3*4', "(1 + 2) * (2 *3)", "(3 * 2) - (1 + 2 * 3)", '7 * (9 - (3 + 2))',
                 '5 + 3', '(1 + 2) * (3 + 4)', '7 * (9-(3+2))', '3 + (2 - 3 * (1 + 2 + ( 4 * 2 - 1)))']
    for tc in test_case:
        tokens = splitTokens(tc)
        result += [infixToPostfix(tokens)]
    return result


if __name__ == "__main__":
    print(test())

 

 

중위 표현식 → 후위 표현식 최종 계산

import infixToPostfix


def postfixEval(tokenList):
    valStack = []

    for token in tokenList:
        if type(token) is int:
            valStack.append(token)
        elif token == '*':
            v1 = valStack.pop()
            v2 = valStack.pop()
            result = v2 * v1
            valStack.append(result)
        elif token == '/':
            v1 = valStack.pop()
            v2 = valStack.pop()
            result = v2 / v1
            valStack.append(result)
        elif token == '+':
            v1 = valStack.pop()
            v2 = valStack.pop()
            result = v2 + v1
            valStack.append(result)
        elif token == '-':
            v1 = valStack.pop()
            v2 = valStack.pop()
            result = v2 - v1
            valStack.appned(result)
    return valStack.pop()

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

def test():
    result = []
    eval_r = []
    test_case = ['5 + 3', '(1 + 2) * (3 + 4)', '7 * (9-(3+2))', '3 + (2 - 3 * (1 + 2 + ( 4 * 2 - 1)))']
    for tc in test_case:
        result += [solution(tc)]
        eval_r += [eval(tc)]
    return "result : {} \neval: {}".format(result, eval_r)



if __name__ == "__main__":
    
    print(test())

 

중위 표현식 → 후위 표현식 최종 계산

import infixToPostfix


def postfixEval(tokenList):
    valStack = []

    for token in tokenList:
        if type(token) is int:
            valStack.append(token)
        elif token == '*':
            v1 = valStack.pop()
            v2 = valStack.pop()
            result = v2 * v1
            valStack.append(result)
        elif token == '/':
            v1 = valStack.pop()
            v2 = valStack.pop()
            result = v2 / v1
            valStack.append(result)
        elif token == '+':
            v1 = valStack.pop()
            v2 = valStack.pop()
            result = v2 + v1
            valStack.append(result)
        elif token == '-':
            v1 = valStack.pop()
            v2 = valStack.pop()
            result = v2 - v1
            valStack.appned(result)
    return valStack.pop()

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

def test():
    result = []
    eval_r = []
    test_case = ['5 + 3', '(1 + 2) * (3 + 4)', '7 * (9-(3+2))', '3 + (2 - 3 * (1 + 2 + ( 4 * 2 - 1)))']
    for tc in test_case:
        result += [solution(tc)]
        eval_r += [eval(tc)]
    return "result : {} \neval: {}".format(result, eval_r)



if __name__ == "__main__":
    
    print(test())