스택(stack)

1. 스택의 특징

가장 기본적인 자료구조라 할 수 있는 스택(stack)

스택은 LIFO(Last in First Out) 원칙을 따른다.

예를 들면 박스에 책을 놓으면 차례대로 마지막에 넣은것부터 빼내는듯 하는것과 같다.

주로 재귀 알고리즘과 실행 취소같은 작업을 할때 쓰인다.

2. 스택의 장단점

○장점

   1. 구조가 단순해서 구현하기 쉽다.

   2. 삽입과 삭제의 속도가 빠르다.

○단점

   1. 맨 위의 원소만 접근할 수 있다.

   2. 탐색을 하려면 가장 먼저 push된 데이터부터 하나하나 꺼내서 옮겨야 한다.

3. 시간 복잡도

삽입함수 push() : O(1)

삭제함수 pop() : O(1)

가장 위에 있는 값을 return하는 함수 : O(1)

4. 스택 구현

class Stack:
    def __init__(self):
        self.items = []
    def push(self, val):
        self.items.append(val)

    def pop(self):
        try:
            return self.items.pop()
        except IndexError:
            print("Stack is empty")

    def top(self):
        try:
            return self.items[-1]
        except IndexError:
            print("Stack is empty")

    def __len__(self):
        return len(self.items)

    def isEmpty(self):
        return self.__len__() == 0

5. 스택을 이용한 계산기

스택을 사용해서 계산기를 만들 수 있다.

우리가 흔히 쓰는 수식은 infix표현으로 되어있는데 

postfix표현으로 바꾸면 스택으로 수식을 계산할 수 있다. 

 

infix : 일반적인 수식의 표기법, 두개의 피연산자 사이 연산자가 있는 표현방법 [예 : (5+7)/3-5]

postfix :  연산자를 피연산자의 뒷쪽에 표시하는 표현방법 [예 : 57+3/5-]

 

class Stack:
    def __init__(self):
        self.items = []
    def push(self, val):
        self.items.append(val)

    def pop(self):
        try:
            return self.items.pop()
        except IndexError:
            print("Stack is empty")

    def top(self):
        try:
            return self.items[-1]
        except IndexError:
            print("Stack is empty")

    def __len__(self):
        return len(self.items)

    def isEmpty(self):
        return self.__len__() == 0

def get_token_list(expr):		#expr 문자열을 피연산자와 연산자로 나눈 후 리스트에 담는 함수
    token_list=[]		 	#infix를 postfix로 바꾸기 위한 사전작업
    expr=expr.replace(' ','')# 공백 없애기
    listexpr=list(expr)
    while listexpr:
        if listexpr[0] in '+*-/^()':
            token_list.append(listexpr[0])
            del listexpr[0]
        else:
            if len(listexpr)==1:
                token_list.append(listexpr[0])
                del listexpr[0]
            else:
                for i in range(1,len(listexpr)):     
                    if listexpr[i] in '+*-/^()':
                        token_list.append(''.join(listexpr[0:i]))
                        del listexpr[0:i]
                        break
                    elif i==len(listexpr)-1:
                        token_list.append(''.join(listexpr[0:len(listexpr)]))
                        del listexpr[0:len(listexpr)]
                        break
    return token_list
                        
def infix_to_postfix(token_list):#infix인 수식을 postfix로 바꾸는 함수
    outstack=[]
    opstack=Stack()
    #연산자 우선순위 설정
    prec={}
    prec['(']=0
    prec['+']=1
    prec['-']=1
    prec['*']=2
    prec['/']=2
    prec['^']=3

    for i in token_list:
        if i not in '+-*/^()':#연산자 피연산자 판별
            outstack.append(i)
        elif i =='(':
            opstack.push(i)
        elif i ==')':
            while True:
                outstack.append(opstack.pop())
                if opstack.top()=='(':
                    opstack.pop()
                    break
        else:
            if opstack.isEmpty():
                opstack.push(i)
            elif prec[i]>prec[opstack.top()]:
                opstack.push(i)
            elif prec[i]<=prec[opstack.top()]:
                while True:
                    if opstack.isEmpty():
                        opstack.push(i)
                        break
                    elif prec[i]>prec[opstack.top()]:
                        opstack.push(i)
                        break
                    elif prec[i]<=prec[opstack.top()]:
                        outstack.append(opstack.pop())
                        continue
    while not opstack.isEmpty():
        outstack.append(opstack.pop())	
    while True:
        try:
            outstack.remove('(')
            outstack.remove(')')
        except ValueError:
            break
    return outstack
def compute_postfix(token_list):#postfix수식을 계산하는 함수
    resultstack=Stack()
    for i in token_list:
        if i not in '+-*/^':
            resultstack.push(float(i))
        elif i=='+':
            next_num=resultstack.pop()
            previous_num=resultstack.pop()
            resultstack.push(previous_num+next_num)
        elif i=='-':
            next_num=resultstack.pop()
            previous_num=resultstack.pop()
            resultstack.push(previous_num-next_num)
        elif i=='*':
            next_num=resultstack.pop()
            previous_num=resultstack.pop()
            resultstack.push(previous_num*next_num)
        elif i=='/':
            next_num=resultstack.pop()
            previous_num=resultstack.pop()
            resultstack.push(previous_num/next_num)
        elif i=='^':
            next_num=resultstack.pop()
            previous_num=resultstack.pop()
            resultstack.push(previous_num**next_num)
    return resultstack.pop()
			
expr = input()
value = compute_postfix(infix_to_postfix(get_token_list(expr)))
print(value)