[2024.02.13] Stack 2

체리마루·2024년 2월 13일

계산기1

문자열로 된 계산식이 주어질 때, 스택을 이용하여 이 계산식의 값을 계산할 수 있다.
문자열 수식 계산의 일반적 방법
step1. 중위 표기법의 수식을 후위 표기법으로 변경한다. (스택 이용)
step2. 후위 표기법의 수식을 스택을 이용하여 계산한다.
step1. 중위표기식의 후위표기식 변환 방법1
1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
2) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.
3) 괄호를 제거한다.

코드를 입력하세요

'''
(6+5*(2-8)/2)
'''

top = -1
stack = [0] * 100

icp = {'(':3, '*':2, '/':2, '+':1, '-':1} #스택 밖에서의 우선순위
isp = {'(':0, '*':2, '/':2, '+':1, '-':1} #스택 안에서의 우선순위

fx = '(6+5*(2-8)/2)'
postfix = ''

for tk in fx:
    #여는 괄호 push, 연산자이고 top 원소보다 우선순위가 높으면 push
    if tk == '(' or (tk in '*/+-' and isp[stack[top]] < icp[tk]):
        top += 1 #push
        stack[top] = tk

    #연산자이고 top 원소보다 우선순위가 높지 않으면 pop
    elif tk in '*/+-' and isp[stack[top]] >= icp[tk]:
        #top 원소의 우선순위가 낮을 때까지 pop
        while isp[stack[top]] >= icp[tk]:
            top -= 1 #pop
            postfix += stack[top+1]
        top += 1 #push
        stack[top] = tk

    #닫는 괄호면, 여는 괄호를 만날 때까지 pop
    elif tk == ')':
        while stack[top] != '(':
            top -= 1 #pop
            postfix += stack[top+1]
        top -= 1 #여는 괄호 pop해서 버림
        #stack[top+1] #???

    #피연산자인 경우
    else:
        postfix += tk

print(postfix)

강사님 코드1

#중위식 -> 후위식 (스택)
text = '(1+(1+3)*4/5)'

stack = [] #push: append(x) / pop: pop()
result = '' #후위식을 넣을 result 변수

#스택의 상태가 항상 내가 넣으려고 하는 연산자가,
#기존에 있었던 연산자보다 우선순위가 높도록 유지!
#중위식을 순회하며 후위식을 만들어야 한다.

for ch in text:
    #1. 숫자(피연산자)가 나오면 그대로 출력
    if ch.isdigit():
        result += ch

    #2. '(' 나오면
    elif ch == '(':
        stack.append('(') #'('를 스택에 push한다

    #3. '*' '/' 나오면
    elif ch == '*' or ch == '/':
        #스택에 들어있는 값이 * / 연산자라면 빼준다
        if len(stack) > 0 and (stack[-1] == '*' or stack[-1] == '/'):
            result += stack.pop()
        stack.append(ch)

    #4. '+' '-' 나오면
    elif ch == '+' or ch == '-':
        #여는 괄호가 나오거나 스택이 아예 비는 경우까지 pop을 계속 진행해준다
        while len(stack) > 0 and stack[-1] != '(':
            result += stack.pop()
        stack.append(ch)

    #5. ')' 나오면
    elif ch == ')':
        #여는 괄호가 나올 때까지 pop해준다
        while stack[-1] != '(':
            result += stack.pop()
        stack.pop()

#순회가 끝난 후, stack의 내용을 모두 pop해준다
while len(stack) > 0:
    result += stack.pop()

print(result)

강사님 코드2

#중위식 -> 후위식 (스택)
text = '(1+(1+3)*4/5)'

stack = [] #push: append(x) / pop: pop()
result = '' #후위식을 넣을 result 변수

icp = {'(': 3, '*': 2, '/': 2, '+': 1, '-': 1} #입력될 때의 연산자 우선순위
isp = {'(': 0, '*': 2, '/': 2, '+': 1, '-': 1} #스택 내에 있을 때의 연산자 우선순위

#스택의 상태가 항상 내가 넣으려고 하는 연산자가,
#기존에 있었던 연산자보다 우선순위가 높도록 유지!
#중위식을 순회하며 후위식을 만들어야 한다.

for ch in text:
    #숫자(피연산자)가 나오면 그대로 출력
    if ch.isdigit():
        result += ch

    if ch in '*/+-(':
        #1. 입력된 연산자 우선순위 > 스택 맨 위의 연산자 우선순위
        if len(stack) == 0 or icp[ch] > isp[stack[-1]]:
            stack.append(ch)
        #2. 입력된 연산자 우선순위 <= 스택 맨 위의 연산자 우선순위
        else:
            while len(stack) > 0 and icp[ch] <= isp[stack[-1]]:
                result += stack.pop()
            stack.append(ch)

    #')' 나오면
    elif ch == ')':
        #여는 괄호가 나올 때까지 pop해준다
        while stack[-1] != '(':
            result += stack.pop()
        stack.pop()

#순회가 끝난 후, stack의 내용을 모두 pop해준다
while len(stack) > 0:
    result += stack.pop()

print(result)

계산기2

step2. 후위 표기법의 수식을 스택을 이용하여 계산

1) 피연산자를 만나면 스택에 push 한다.
2) 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 연산결과를 다시 스택에 push 한다.
3) 수식이 끝나면, 마지막으로 스택을 pop하여 출력한다.

강사님 코드1

#계산기2 (후위식->계산하여 결과)

postfix = '113+4*5/+'
stack = [] #스택

for ch in postfix:
    #피연산자를 스택에 넣는다
    if ch.isdigit():
        stack.append(ch)

    #연산자를 만나면 피연산자를 두개 빼서 연산. stack에 push
    else: #연산자 * / + -
        b = int(stack.pop())
        a = int(stack.pop())
        if ch == '*':
            stack.append(a * b)
        elif ch == '/':
            stack.append(a / b)
        elif ch == '+':
            stack.append(a + b)
        elif ch == '-':
            stack.append(a - b)

#순회가 완료되면 스택에 단 하나의 결과값만이 남게 된다
result = stack.pop()
print(result)

강사님 코드2

#계산기2 (후위식->계산하여 결과)

#연산자들을 딕셔너리에 lambda식으로 표현
oper = { #연산자 - 람다식 쌍
    '*': lambda a, b: a * b,
    '/': lambda a, b: a // b,
    '+': lambda a, b: a + b,
    '-': lambda a, b: a - b
}

postfix = '113+4*5/+'
stack = [] #스택

for ch in postfix:
    #피연산자를 스택에 넣는다
    if ch.isdigit():
        stack.append(ch)

    #연산자를 만나면 피연산자를 두개 빼서 연산. stack에 push
    else: #연산자 * / + -
        b = int(stack.pop())
        a = int(stack.pop())
        stack.append(oper[ch](a, b))

#순회가 완료되면 스택에 단 하나의 결과값만이 남게 된다
result = stack.pop()
print(result)

백트래킹

백트래킹(Backtracking) 기법은 해를 찾는 도중에 '막히면' (즉, 해가 아니면) 되돌아가서 다시 해를 찾아 가는 기법이다.
백트래킹 기법은 최적화 문제와 결정 문제를 해결할 수 있다.
결정 문제: 문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'no'가 답하는 문제 ex) 미로찾기, n-Queen 문제, Map coloring, 부분 집합의 합 문제 등

1) 상태 공간 트리의 깊이 우선 검색을 실시한다.
2) 각 노드가 유망한지를 점검한다.
3) 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색을 계속한다.

부분집합

어떤 집합의 공집합과 자기자신을 포함한 모든 부분집합을 powerset이라고 하며 구하고자 하는 어떤 집합의 원소 개수가 n일 경우 부분집합의 개수는 2^n개 이다.
백트래킹 기법으로 powerset 만들기
n개 원소가 들어있는 집합의 2^n개의 부분집합을 만들 때는, true 또는 false값을 가지는 항목들로 구성된 n개의 배열을 만드는 방법을 이용한다. 여기서 배열의 i번째 항목은 i번째의 원소가 부분집합의 값인지 아닌지를 나타내는 값이다.
powerset을 구하는 백트래킹 알고리즘

def f(i, k):
    if i == k:
        for j in range(k):
            if bit[j]:
                print(arr[j], end=' ')
        print()
    else:
        for j in range(2):
            bit[i] = j
            f(i+1, k)
        '''
        bit[i] = 1
        f(i+1, k)
        bit[i] = 0
        f(i+1, k)
		'''
N = 4
arr = [1, 2, 3, 4]
bit = [0] * N #bit[i]: arr[i]가 부분집합에 포함되었는지 나타내는 배열
f(0, N) #bit[i]에 1 또는 0을 채우고, N개의 원소가 결정되면 부분집합을 출력