Stacks

ADTs(Abstract Data Types)

• 실제로 구현한 디테일을 숨기고 껍데기만 명시한 타입

An ADT specifies

1. Data stored
2. Operations on the data
3. Error conditions associated with operations

The Stack ADT

• push(object)
  : stack에 넣음
• object pop()
  : stack에서 뺌
• object top()
  : 제일 위에 있는 놈 확인
• integer len()
  : stack의 길이 확인
• boolean is_empty()
  : stack 이 비었는지 확인

FILO(First In Last Out, 선입후출) 구조

EX. 웹 브라우저 뒤로가기, TEXT Editor Undo 액션, 파이썬의 activation record

Array-based Stack

• Let n be the number of elements in the stack
• The space used is O(n)
• Each operation runs in time O(1)

Array-based Stack in Python

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 top(self):
    	if self.is_empty():
        	raise Empty('Stack is empty')
        return self._data[-1]
    def pop(self):
    	if self.is_empty():
        	raise Empty('Stack is empty')
        return self._data.pop()

Parentheses Matching

• 괄호 잘 닫기 프로그램
  

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()

HTML Tag Matching

Evaluating Arithmetic Expressions

• 사칙연산 계산

14 - 3 * 2 + 7 = ( 14 - (3*2) ) + 7

• prec 우선 순위
• repeatOps method : 우선 계산
• end token : $

Computing Spans(not in book)

• span을 직역하면 구간
  
• 연속적으로 증가하는 구간의 길이 계산
• 0번 인덱스 값 6, 1번 인덱스 값 3, 2번 인덱스 값 4, 3번 인덱스 값 5, 4번 인덱스 값 2
  
• 지금 인덱스가 다음 인덱스보다 크면 S +1, 작다면 1로 초기화