알고리즘/자료구조 01 - stack, 괄호 검사, PostFix, 수식 계산

Stack

• Stack은 LIFO (Last In First Out)의 선형 자료 구조
• push, pop
• python에서는 list를 통해 list.append(x), list.pop()으로 사용한다.

 

push, overflow

## push
stack = []
for now in range(1, 6):
    stack.append(now)
print(stack)
# [1, 2, 3, 4, 5]

## overflow, push
stack = [0]*3
top  = -1
for now in range(1, 6):
    top += 1
    if top >= len(stack):
        print("overflow")
        break
    stack[top] = now
print(stack)
# overflow
# [1, 2, 3]

 

pop, underflow

## pop1
stack = []
def pop1():
    if len(stack) == 0:
        # underflow
        return
    else:
        return stack.pop()

## pop2
stack = [0]*10
top = -1

def pop2():
    global top
    if top == -1:
        # underflow
        return
    item = stack[top]
    top -= 1
    return item

 

stack에 1부터 5까지 넣고 출력하기

## stack에 1부터 5까지 넣고 출력하기

### 방법1
stack = []
for now in range(1, 6):
    stack.append(now)

while stack:
    print(stack.pop())

### 방법2
stack = [0]*10
top = -1

for now in range(1, 6):
    top += 1
    stack[top] = now

while top != -1:
    print(stack[top])
    top -= 1
# 5
# 4
# 3
# 2
# 1

 

괄호 검사

https://www.acmicpc.net/problem/9012

def isParenthis(myStr):
    stack = []
    for s in myStr:
        if s == '(':
            stack.append(s)
        elif s == ')':
            if len(stack) == 0:
                return False
            if stack[-1] == '(':
                stack.pop()
            else:
                return False
    else:
        if len(stack) == 0:
            return True
        else:
            return False


n = int(input())
for _ in range(n):
    data = str(input())
    if isParenthis(data):
        print("YES")
    else:
        print("NO")

 

PostFix

https://www.acmicpc.net/problem/1918

Data = input() # A*(B+C) -> ABC+*

icp = {'(':3, '+':1, '-':1, '*':2, '/':2} # in-coming priority
isp = {'(':0, '+':1, '-':1, '*':2, '/':2} # in-stack priority

stack = []
postFix = ''

for now in Data:
    if now == ')':
        if len(stack) != 0 and stack[-1] == '(':
            stack.pop()
        else:
            while len(stack) != 0 and stack[-1] != '(':
                postFix += stack.pop()
            stack.pop() # '(' 꺼내기
    elif now in icp.keys():
        if len(stack) == 0:
            stack.append(now)
        elif icp[now] > isp[stack[-1]]:
            stack.append(now)
        elif icp[now] <= isp[stack[-1]]:
            while stack and icp[now] <= isp[stack[-1]]:
                postFix += stack.pop()
            stack.append(now)
    else: # 숫자, 혹은 문자면
        postFix += now
while stack:
    postFix += stack.pop()
print(postFix)

 

수식의 계산

https://www.acmicpc.net/problem/1935

import sys
sys.stdin = open("input.txt", 'r')

n = int(input())
Data = input() # ABC*+DE/-
operands = [0] # 1
alpToNum = [0] # A
for _ in range(n):
    operands.append(int(input()))

stack = []
for now in Data:
    # if now.isdigit():
    #     stack.append(int(now))
    if now not in ['*', '/', '+', '-']:
        if now not in alpToNum:
            alpToNum.append(now)
        idx = alpToNum.index(now)
        stack.append(operands[idx])
    else:
        if len(stack) != 0:
            a = stack.pop()
            b = stack.pop()
            if now == '+':
                stack.append(b+a)
            elif now == '-':
                stack.append(b-a)   
            elif now == '*':
                stack.append(b*a)          
            elif now == '/':
                # stack.append(b//a) 
                stack.append(b/a)   
    # print(stack)
print('%.2f' %stack[-1]) # 소수점 둘째 자리까지 출력
# print('%.10f' %1.2345)