Example using Stack in Python

1. Stack 클래스 정의

from queue import Empty

class ArrayStack:

    def __init__(self):
        self._data = []
    
    def __len__(self):
        return len(self._data)

    def is_empty(self):
        return len(self._data) == 0

    def push(self, e):
        self._data.append(e)

    def pop(self):
        if self.is_empty():
            raise Empty('Stack is empty')
        return self._data.pop()

    def top(self):
        if self.is_empty():
            raise Empty('Stack is empty')
        return self._data[-1]

---

2. 소 · 중 · 대괄호로 묶인 표현식의 검증

def is_matched(expr):
    lefty = "({["
    righty = ")}]"
    S = ArrayStack()

    for c in expr:
        if c in lefty:
            S.push(c)
        elif c in righty:
            if S.is_empty():
                return False
            if righty.index(c) != lefty.index(S.pop()):
                return False
    return S.is_empty()

---

3. html 스크립트 검증

def is_matched_html(raw):
    S = ArrayStack()
    j = raw.find("<")
    while j != -1:
        k = raw.find(">", j+1)
        tag = raw[j+1:k]
        if k == -1:
            return False
        if not tag.startswith("/"):
            S.push(tag)
        else:
            if S.is_empty():
                return False
            if tag[1:] != S.pop():
                return False
        j = raw.find("<", k+1)
    return S.is_empty()

1. "<"를 찾음

2. ">"를 찾음

3. 사이의 문자열을 스택에 저장

4. 2.에서 찾은 ">" 뒤의 "</"를 찾음

5. 있으면 뒤의 문자열을 스택.pop()과 비교, 없으면 1.로 돌아감

---

4. 임의의 종목이 며칠만의 상한가인지를 기록한 list를 반환

def cal_span(X):
    A = ArrayStack()
    S = [0 for _ in range(len(X))]
    for i in range(len(X)):
        while (not A.is_empty()) and (X[A.top()] <= X[i]):
            A.pop()
        if A.is_empty():
            S[i] = i + 1
        else:
            S[i] = i - A.top()
            print(str(i) + " - " + str(A.top()))
        A.push(i)
        print(A._data)
    return S

1. A라는 스택에 현재 관찰중인 시기의 인덱스 i를 저장

2. 종목의 주가[i]와 주가[i+1]을 비교

3. 후자가 더 크면 A.pop()하며 더 과거의 주가와 비교

4. 전자가 커질 때까지 비교

5. 전자가 커진 만큼의 기간을 리스트 S에 저장