어서와! 자료구조와 알고리즘은 처음이지? 13강 실습: 후위표현 수식 계산
인자로 주어진 문자열 expr 은 소괄호와 사칙연산 기호, 그리고 정수들로만 이루어진 중위 표현 수식입니다. 함수 solution()
은 이 수식의 값을 계산하여 그 결과를 리턴하도록 작성되어 있습니다. 이 함수는 차례로 splitTokens()
, infixToPostfix()
, 그리고 postfixEval()
함수를 호출하여 이 수식의 값을 계산하는데,
splitTokens()
- 강의 내용에서와 같은 코드로 이미 구현되어 있습니다.infixToPostfix()
- 지난 강의의 연습문제에서 작성했던 코드를 수정하여, 문자열이 아닌 리스트를 리턴하도록 작성합니다.postfixEval()
- 이번 강의의 연습문제입니다. 함수의 내용을 완성하세요.즉, 두 개의 함수 infixToPostfix()
와 postfixEval()
을 구현하는 연습입니다. 스택을 이용하기 위하여 class ArrayStack
이 정의되어 있으므로 그것을 활용하세요.
[참고] Python 에는 eval()
이라는 built-in 함수가 있어서, 이 함수에 문자열을 인자로 전달하면, 그 문자열을 그대로 Python 표현식으로 간주하고 계산한 결과를 리턴하도록 되어 있습니다. 이 built-in 함수 eval()
을 이용하면 이 연습문제는 전혀 직접 코드를 작성하지 않고도 정답을 낼 수 있을 것이지만, 스택을 이용하여 중위표현식을 계산하는 프로그래밍 연습을 위한 것이니, 강의 내용에서 설명한 절차를 수행하도록 코드를 작성해 보세요.
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 -> 중위 표현식으로된 수식
def splitTokens(exprStr):
tokens = []
val = 0 # 각 자리 숫자를 담는 변수
valProcessing = False #
for c in exprStr:
# 빈칸이 들어있으면 그냥 넘어감
if c == ' ':
continue
# 숫자를 만나면 10진수로 변환하는 과정
if c in '0123456789' :
val = val * 10 + int(c)
valProcessing = True # 수를 만났으므로 true
# 숫자가 아니라면 (괄호 또는 연산자를 만났다고 간주) 10진수 표현이 끝난것
else:
if valProcessing:
tokens.append(val)
val = 0
valProcessing = False # 지금 10진수를 처리하고있지 않다
tokens.append(c)
# 마지막 수 처리
if valProcessing:
tokens.append(val)
return tokens
# 중위 표기법 -> 후위 표기법으로 바꾸는 함수
def infixToPostfix(tokenList):
prec = {
'*' : 3,
'/' : 3,
'+' : 2,
'-' : 2,
'(' : 1
}
opStack = ArrayStack()
postfixList = []
for token in tokenList:
# 피연산자이면 리스트에 추가
if type(token) is int:
postfixList.append(token)
# '('이면 스택에 push
elif token == '(':
opStack.push(token)
# ')' 이면 '('가 나올때까지 pop
elif token == ')':
while opStack.peek() != '(':
postfixList.append(opStack.pop())
opStack.pop()
# 연산자이면 +-*/
else:
# 스택이 비어있을 경우 스택에 push
if opStack.isEmpty():
opStack.push(token)
# 스택이 비어있지 않다면 비교
else:
# 스택에 값이 존재할 동안에 반복
while opStack.size() > 0:
# 우선 순위가 스택안에 있는게 높으면 꺼낸다
if prec[opStack.peek()] >= prec[token]:
postfixList.append(opStack.pop())
else:
break
opStack.push(token)
# 반복문을 다 돌고 스택이 빌때까지 pop
while not opStack.isEmpty():
postfixList.append(opStack.pop())
# 리스트로 리턴한다
return postfixList
# 후위 표기법을 계산하는 함수
def postfixEval(tokenList):
valStack = ArrayStack()
for token in tokenList:
# 피연산자를 만나면 스택에 push
if type(token) is int:
valStack.push(token)
# 연산자를 만나면
elif token == '+':
n1 = valStack.pop()
n2 = valStack.pop()
valStack.push(n2+n1)
elif token == '-':
n1 = valStack.pop()
n2 = valStack.pop()
valStack.push(n2-n1)
elif token == '*':
n1 = valStack.pop()
n2 = valStack.pop()
valStack.push(n2*n1)
elif token == '/':
n1 = valStack.pop()
n2 = valStack.pop()
valStack.push(int(n2/n1))
return valStack.pop()
I swear I will read your content more often because slope io this is a game I just found out about recently, and whenever you have some free time I would love to have you play it with me.
공부하는데 많은 도움이 되고 있습니다! 중위표현식으로 바꾸는 과정에서 음의 정수나 소수점자리까지 처리할 수 있을까요? 고민해보았는데 실력이 부족해서 그런지 방법이 떠오르지 않네요ㅜ