탐색, 자료구조, 알고리즘
(스택응용) 중위표현식 후위표현식 변환
데이터왕
2023. 12. 23. 15:25
In [ ]:
#연습문제- 수식의 괄호 유효성 검사
'''올바른 수식 : (A+B), {(A+B)*C}, {(A+B)*(C+D)}
올바르지 않은: (A+B, {(A+B}*C), [(A+B)*(C+D)}
여는괄호 만나면 push /
닫는 괄호 만나면
1 스택이 비어있으면 틀림
2 스택에서 pop, 쌍을 이루는 괄호인지 검사
끝까지 검사한후 스택이 비어있어야함'''
In [18]:
#12강 (스택의 응용) 수식의 후위표기법
'''중위 표기법과 후위 표기법
중위표기법 : (A+B)*(C+D) - 연산자가 피연산자들의 사이에 위치
후위표기법 : AB+CD+* - 연산자가 피연산자들의 뒤에 위치
중위표현식-> 후위표현식으로 바꾸는 알고리즘
스택에 이미 저장된 기호가 우선순위가 같거나 크면 사용한다.
A*B+C -> AB*C+
1 후위 A
2 스택 *
3 후위 AB
+나왔는데 스택이 비어있지 않아 우선순위 비교 (*먼저)
4 후위 AB* 스택 +
5 후위 AB*C 스택 +
6 끝남/ 후위 AB*C+ 스택
A+B*C ->ABC*+
1 후위 A
2 스택 +
3 후위 AB
*나왔는데 스택이 비어있지 않아 우선순위 비교 (*먼저)
4 스택 +*
5 후위 ABC
6 끝남/ 후위 ABC* 스택 +
7 후위 ABC*+ 스택
A+B+C
1 후위 A
2 스택 +
3 후위 AB
+나왔는데 스택이 비어있지 않아 우선순위 비교 (같음)
4 후위 AB+ 스택 +
5 후위 AB+C
6 끝남/ 후위 AB+C+ 스택
(A+B)*C :괄호가 있으면 우선순위가 괄호안
괄호 안 먼저 계산하는 알고리즘 : 여는 괄호는 스택에 PUSH
닫는 괄호 만나면 여는 괄호 나올 때까지 POP
1 스택 (
2 후위 A
3 스택 ( +
4 후위 AB
+닫는 괄호 만나면 여는 여는 괄호 나올 때까지 POP
5 후위 AB+ 스택
6 스택 *
7 후위 AB+C
8 끝남/ 후위 AB+C* 스택
후위 AB+C*
A*(B+C) : 괄호가 뒤에 있을때
연산자를 만났을 때, 여는 괄호 너머까지 POP 하지 않도록
여는 괄호의 우선순위는 가장 낮게 설정, 닫는괄호를 만났을때
여는 괄호가 나올때까지 POP
* ( +
)나오면 ( 나올때까지 pop
1 후위 A
2 스택 *
3 스택 * (
4 후위 AB
5 스택 * ( +
6 후위 ABC
닫는괄호! 여는괄호까지 pop
7 후위 ABC+ 스택 *
8 끝남/ 후위 ABC+* 스택
후위 ABC+*
(A+B)*(C+D)
1 스택 (
2 후위 A
3 스택 ( +
4 후위 AB
닫는괄호! 여는괄호까지 pop
5 후위 AB+ 스택
6 스택 *
7 스택 * (
8 후위 AB+C
9 스택 * ( +
10 후위 AB+CD
닫는괄호! 여는괄호까지 pop
11 AB+CD+
12 끝/ AB+CD+*
(A+(B-C))*D
1 스택 (
2 후위 A
3 스택 ( +
4 스택 ( + (
5 후위 AB
6 스택 ( + (-
7 후위 ABC
닫는괄호! 여는괄호까지 pop
8 후위 ABC- 스택 ( +
닫는괄호! 여는괄호까지 pop
9 후위 ABC-+ 스택
10 스택 *
11 후위 ABC-+D
12 끝/ 후위 ABC-+D* 스택
A*(B-(C+D))
1 후위 A
2 스택 *
3 스택 * (
4 후위 AB
5 스택 * ( -
6 스택 * ( - (
7 후위 ABC
8 스택 * ( - ( +
9 후위 ABCD
닫는괄호! 여는괄호까지 pop
10 후위 ABCD+ 스택 * ( -
닫는괄호! 여는괄호까지 pop
11 후위 ABCD+- 스택 *
12 끝 / 후위 ABCD+-* 스택
우선순위 ( + * 순서
우선순위는 낮은순부터 쌓는다.(끝났거나, 닫힌괄호일때 꺼냄)
넣으려는게 우선순위가 더 높다면 그때 그때 꺼내씀
여는 괄호는 예외 그냥 쌓아줌
알고리즘 설계
1 증위 표현식을 왼쪽부터 한 글자씩 읽어서
2 피연산자면 그냥 출력
3 ( 이면 push
4 ) 면 ( 나올 때까지 스택에 pop,출력
5 연산자면 스택에서 이보다 높(거나 같)은 우선순위 것들을 pop
하고 이 연산자는 push
+꺼내지 않고 확인만 하는법 peek()
스택의 연산자 모두 pop() 하는 순환문
while not opStack.isEmpty():'''
1
Out[18]:
1In [ ]:
#12강 실습: 중위표현 수식 -> 후위표현 수식
class ArrayStack:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def push(self, item):
self.data.append(item)
def pop(self):
return self.data.pop()
def peek(self):
return self.data[-1]
prec = {
'*': 3, '/': 3,
'+': 2, '-': 2,
'(': 1
}
def solution(S):
opStack = ArrayStack()
answer = ''
for i in range(len(S)):
if S[i] not in prec and S[i] != ')':
answer +=S[i]
else:
if S[i]=='(':
opStack.push(S[i])
elif S[i]==')':
# ( 나올때까지 pop해서 더해줌
while opStack.peek() != '(':
answer +=opStack.pop()
#남은 ( 도 제거
opStack.pop()
else:
#스택 비어있으면 우선 채워줌
if opStack.isEmpty():
opStack.push(S[i])
else:
#스택 안에 부호 우선순위가 낮으면 쌓아줌
if prec[opStack.peek()]<prec[S[i]]:
opStack.push(S[i])
#아니면 스택 제거후 새로 넣어줌
else:
while not opStack.isEmpty() and prec[opStack.peek()] >= prec[S[i]]:
answer +=opStack.pop()
opStack.push(S[i])
#남아있는것까지 처리
while not opStack.isEmpty():
answer+=opStack.pop()
return answer
In [ ]:
#13강 후위 표기 수식 계산
'''AB+CD+*
1스택 A
2스택 AB
연산자발견
3 A+B 스택
4 스택 A+B
5 스택 A+B C
6 스택 A+B C D
연산자발견
7 C+D 스택 A+B
8 스택 A+B C+D
연산자발견
9 A+B * C+D 스택
10 스택 A+B * C+D
11 끝/ A+B * C+D 스택 -> 리턴 A+B * C+D
피연산자면 스택에 PUSH
연산자 만나면 스택에서 POP 2번
결과를 스택에 PUSH
수식의 끝에 도달하면 1개의 원소가 남아있고 그걸 POP'''
class ArrayStack:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def push(self, item):
self.data.append(item)
def pop(self):
return self.data.pop()
def peek(self):
return self.data[-1]
#exprStr(중요표현식) 을 takens에 담을것
def splitTokens(exprStr):
tokens = [] # 결과로 반환할 토큰 리스트
val = 0 # 숫자 토큰의 현재 값
valProcessing = False # 현재 문자열이 숫자 처리 중인지 여부
for c in exprStr:
# 공백 문자는 무시하고 다음 문자로 넘어감
if c == ' ':
continue
if c in '0123456789':
# 숫자 문자를 숫자 값으로 변환하여 현재 값에 추가
val = val * 10 + int(c)
# 현재 문자열이 숫자 처리 중임을 표시
valProcessing = True
else:
# 숫자 처리 중이었던 경우, 숫자 토큰을 리스트에 추가
if valProcessing:
tokens.append(val)
val = 0 # 현재 값 초기화
# 현재 문자열이 숫자 처리 중이 아님을 표시
valProcessing = False
# 연산자 또는 다른 문자를 리스트에 추가
tokens.append(c)
# 문자열이 끝났을 때 숫자 처리 중이었던 경우, 숫자 토큰을 리스트에 추가
if valProcessing:
tokens.append(val)
return tokens
def infixToPostfix(tokenList):
prec = {
'*': 3,
'/': 3,
'+': 2,
'-': 2,
'(': 1,
}
opStack = ArrayStack()
postfixList = []
for i in range(len(tokenList)):
if tokenList[i] not in prec and tokenList[i] != ')':
postfixList.append(tokenList[i])
else:
if tokenList[i]=='(':
opStack.push(tokenList[i])
elif tokenList[i]==')':
#( 나올때까지 pop해서 더해줌
while opStack.peek() != '(':
postfixList.append(opStack.pop())
#남은 ( 도 제거
opStack.pop()
else:
#스택 비어있으면 우선 채워줌
if opStack.isEmpty():
opStack.push(tokenList[i])
else:
#스택 안에 부호 우선순위가 낮으면 쌓아줌
if prec[opStack.peek()]<prec[tokenList[i]]:
opStack.push(tokenList[i])
#아니면 스택 제거후 새로 넣어줌
else:
while not opStack.isEmpty() and prec[opStack.peek()] >= prec[tokenList[i]]:
postfixList.append(opStack.pop())
opStack.push(tokenList[i])
#남아있는것까지 처리
while not opStack.isEmpty():
postfixList.append(opStack.pop())
return postfixList
def postfixEval(tokenList):
opStack=ArrayStack()
x = ['*','/','+','-']
for i in range(len(tokenList)):
if tokenList[i] not in x:
opStack.push(tokenList[i])
else:
b=opStack.pop()
a=opStack.pop()
if tokenList[i]=='*':
opStack.push(a*b)
elif tokenList[i]=='/':
opStack.push(a/b)
elif tokenList[i]=='+':
opStack.push(a+b)
else:
opStack.push(a-b)
return(opStack.pop())
def solution(expr):
# 중위 표기법 수식을 토큰 리스트로 분리
tokens = splitTokens(expr)
# 중위 표기법을 후위 표기법으로 변환
postfix = infixToPostfix(tokens)
# 후위 표기법을 계산하여 결과값 반환
val = postfixEval(postfix)
return val
In [ ]: