우리가 하는 산수방식(중위 표기법)은 컴퓨터가 이해하는 방식이 아님
중위 표현식
후위 표현식
토큰 | isp (stack top, 내부) 비교대상 | icp (자신, 외부) |
---|---|---|
) | - | - |
* ,/ | 2 | 2 |
+ ,- | 1 | 1 |
( | 0 | 3 |
중위 표현식으로 된 식을 순회할 것
토큰을 담을 빈 스택을 만든다.
토큰이 연산자인 경우
push
(
면 스택에 push
top
에 존재하는 토큰의 isppush
top
에 존재하는 토큰의 isp2번
이 만족할 떄까지 스택에서 pop
결과에 push
2번
이 만족하면 스택으로 들어오는 토큰을 스택에 push
)
면(
를 만날때까지 스택에서 pop한 토큰을 결과에 push(
는 결과에 push
하지 않고 pop
만 순회를 마치면 스택이 비어있을 때까지
pop
한 토큰을 결과에 push
infix = '(6 + 5 * ( 2 - 8 ) / 2 )'
stack = []
result = ''
#변환할 식을 순회
for token in infix:
# 토큰이 피연산자인 경우
if token.isdecimal():
result += token
# 토큰이 연산자인 경우
else:
# 스택이 비어있는 경우, 스택에 push
if not stack:
stack.append(token)
else:
# (는 incoming 우선순위가 가장 높음
if token == '(':
stack.append(token)
# )는 (가 나올때까지 스택에서 pop, result에 append
elif token == ')':
while stack[-1] != '(':
result += stack.pop()
stack.pop()
# incoming 우선순위기 2인 걍우
elif token == '*' or token == '/':
# 스택의 top의 토큰이 우선순위가 낮을 때까지 스택에서 pop, result append
while stack and stack[-1] == '*' or stack[-1] == '/':
result += stack.pop()
stack.append(token)
# incoming 우선순위기 1인 걍우
elif token == '+' or token == '-':
# 스택의 top의 토큰이 우선순위가 낮을 때까지 스택에서 pop, result append
# (가 아닌 경우 모두 동치
while stack and stack[-1] != '(':
result += stack.pop()
stack.append(token)
while stack:
result += stack.pop()
print(result) #6528-*2/+
# 계산하기
# 피연산자
# 스택에 push
# 연산자
# 스택에 담겨잇는 2개의 토큰을 pop 후 연산 후 stack에 push
미로찾기 알고리즘
백트래킹과 깊이 우선탐색과의 차이
백트래킹 기법
백트래킹 알고리즘 절차
1. 상태 공간 트리의 깊이 우선 검색을 실시
2. 각 노드가 유망한지를 점검
3. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색을 계속한다.
어떤 집합의 공집합과 자기 자신을 포함한 모든 부분집합을 powerset이라고 하며 구하고자 하는 어떤 집합의 원소 개수가 n일 경우 부분집합의 개수는 2^n개 이다
백트래킹 기법으로 powerset 구하기
def backtrack(a, k, input) :
global MAXCANDIDATEDS
c = [0] * MAXCANDIDATES
if k == input :
process_solution(a,k) # 답이면 원하는 작없을 한다
else:
k+=1
ncandidates = constrict_candidates(a,k,input,c)
for i in range(ncandidates) :
a[k] = c[i]
backtrack(a,k,input)
def constrict_candidates(a,k,input,c) :
c[0] = True
c[1] = False
return 2
MAXCANDIDATES = 2
NMAX = 4
a = [0] * NMAX
backtrack(a,0,3)
def f(i,k):
if i == k :
print(p)
else:
for j in range(i,K):
p[i], p[j] = p[j], p[i]
f(i+1, k)
p = [1,2,3]
N = len(p)
f(i, N)
알고리즘
def quicksort(a, begin, end) :
if begin < end :
p = partition(a, begin, end)
quicksort(a, begin, p-1)
quicksort(a, p+1, end)