[Python] 스택 활용한 문제(문자열 거꾸로 출력, 괄호의 갯수 판별, 10진수를 n진수로 변환)

1. 문자열 거꾸로 출력

먼저 저번에 올렸던 스택 게시물에서 작성한 스택 class를 간단히 작성해보았습니다.

스택

class Stack(object):
    def __init__(self):
        self.head = None
        self.size = 0

    def push(self, value):
        self.head = Node(value, self.head)
        self.size += 1

    def pop(self):
        if self.head is None:
            print("Stack is Empty!")

        else:
            node = self.head
            self.head = self.head.pointer
            self.size -= 1

            return node.value

    # 스택이 비었다면 True, 아니면 False
    def isEmpty(self):
        if self.size == 0 and self.head is None:
            return True
        else:
            return False

문자열을 거꾸로 출력한다면 많은 방법이 있겠지만 그 중에 스택을 활용해보겠습니다.
스택은 LIFO(후입선출)형태이므로 입력된 문자열을 순서대로 스택에 push한 다음
순서대로 pop을 한다면 간단하게 문자열을 거꾸로 출력이 가능합니다.

문자열 : 파이썬은 쉽고 재밌습니다.
출력 : .다니습밌재 고쉽 은썬이파

스택을 이용해서 문자열 거꾸로 출력

def reversed_string(str1):
    s = Stack()
    reverse = ''
    for i in str1:   # 스택에 순서대로 push
        s.push(i)

    for _ in range(s.size):
        reverse += s.pop()     # 스택의 값들을 pop해서 새로운 문자열에 추가

    return reverse

if __name__ == "__main__":
    str1 = "파이썬은 쉽고 재밌습니다."
    print(str1)
    print(reversed_string(str1))    # .다니습밌재 고쉽 은썬이파

2.단어 단위로 거꾸로 출력하기

문자 전체가 아니라 단어 단위로 뒤집으려면 단어 단위로 스택에 push, pop하면 간단히 작성할 수 있습니다.
예를 들어
문자열 : "파이썬 알고리즘은 너무 재밌습니다."
출력 : "재밌습니다." "너무" "알고리즘은" "파이썬"

단어단위로 거꾸로 출력

def reversed_words(str1):
    s = Stack()

    for w in str1.split(" "):
        s.push(w)

    #while not s.isEmpty():
    while s.head:
        print(s.pop(), end = " ")
    print()

if __name__ == "__main__":
    str1 = "파이썬 알고리즘은 너무 재밌습니다."
    reversed_words(str1)                    # 재밌습니다. 너무 알고리즘은 파이썬 

3.괄호가 올바르게 들어갔는지 확인

문자열을 하나씩 확인해서 만약 '('이라면 스택에 push해줄거고 ')'라면 pop을 해줄겁니다.
스택을 사용하는 이유는 '(())'같이 괄호 끼리의 순서를 판별하기 위해서입니다.
안쪽 괄호가 먼저 닫혀야 정상 괄호가 되기 때문입니다.
더 응용해서 소괄호, 중괄호, 대괄호를 같이 생각해볼 수도 있습니다.

스택을 이용하여 괄호 판별

def balance(str1):
    s = Stack()
    isBalance = True     # 괄호의 정상 유무를 표시할 변수
    index = 0

    # 문자열의 길이만큼 반복 and isBalance가 True동안 반복
    while index < len(str1) and isBalance:
        symbol = str1[index]

        if symbol == '(':
            s.push(symbol)

        elif symbol == ')':
            if s.isEmpty():    # 스택이 비어있는데 ')'가 나온다면
                isBalance = False
            else:
                s.pop()
        index += 1
    # 스택이 비어있다면 괄호의 수 정상(True), 그게 아니라면 비정상(False)
    return isBalance and s.isEmpty()


if __name__ == "__main__":
    str1 = '(())()()'
    str2 = '()((())()'
    print(balance(str1))            # True
    print(balance(str2))            # False

4. 10진수의 수를 2진수로 변환

10진수의 수를 2로 나눈 나머지를 스택에 push하고, 몫이 0이 될때까지 push를 반복합니다.
마지막으로 스택에 저장된 값들을 pop을 한다면, 2진수로 출력이 가능합니다.
2진수 뿐만 아니라 매개변수n을 다른 값으로 활용하여 n진수로 변환하여 출력이 가능합니다.

스택을 이용하여 10진수를 n진수로 변환

def toBinary(num, i):     # 2진수로 바꾸려면 i=2가 된다.
    s = Stack()
    temp = num
    result = ''

    # 2로 나눈 나머지를 스택에 push 반복
    while temp != 0:
        s.push(temp % i)
        temp = temp // i

    # 스택에서 차례대로 pop하여 결과값에 문자열 형식으로 더해준다.
    while s.head:
        result += str(s.pop())
    print()

    return result

if __name__ == "__main__":
    result = toBinary(321, 2)

    print(result)                # 101000001

이상으로 스택을 활용해서 몇몇 응용을 해보았습니다.