[Datastructure] 스택과 활용(2) Infix to Postfix and calculation
Infix, postfix
💡 의미
- Infix 수식은 일반적인 수식 작성법이다.
연산자가 수식 가운데에 존재하는 수식 - Postfix 수식은 수식 내의 연산자가 뒤에 오도록 작성한다.
💡 사용법
- 연산자 우선순위에 따라 괄호를 삽입한다.
- 괄호 내의 연산자를 해당 괄호 오른쪽으로 이동시키는 것을 반복한다.
- 괄호를 모두 지운다.
prefix는 이동방향만 다르다.
Infix►Postfix►Calculation 함수 만들기
💡 문제 정의
3가지 문제로 나뉜다.
- 어떻게 입력을 연산자와 피연산자로 나눌 것인가.
- 어떻게 Postfix로 변환할 것인가.
- 어떻게 Postfix수식을 계산할 것인가
1. ✏️ 연산자와 피 연산자로 나누기
연산자와 피 연산자로 나눌때의 주의점은
❗️
-공백이 있을수도, 없을수도 있다.
-어떻게 문자열로 들어온 숫자를 정수형(실수형) 데이터로 변환할 것인가.
예시
만약 “123a 456” 이 입력된다면,
토큰리스트는 [123,”a”,456] 이 되어야한다.
만약 “ a123b456 ccc”가 입력되면,
토큰리스트는 [“a”,123,”b”,456,”c”,”c”,”c”] 가 되어야한다.
이 문제들의 공통점은
- 공백은 무시한다.
- 문자열이 들어오면 그대로 토큰리스트에 추가한다.
- 숫자가 들어오면 토큰리스트에 추가하지않고, 다음 문자열을 검사한다.
- 만약 다음 문자열이 문자라면, 이전까지 검사한 숫자들을 모두 더한다.
그래서 코드에는
- 공백은 무시한다.
- 숫자문자가 들어오면 이를 저장해 연산할 변수가 필요하다
- 현재 문자열 검사 중에, 전에 숫자형을 검사했었는지, 안했었는지 체킹해야한다.
가 반영되어야한다.
def splittokens(expressions):
tokens = [] #토큰 담을 리스트
valProcessing = False #현재 for문의 char가 숫자를 다루고 있는가 판별
val = 0 #숫자를 다루고 있을때, 계산할 변수
for char in expressions:
if char == " ": #공백을 다룬다면 continue로 for문의 다음 char로
continue
if char in '0123456789': #char가 숫자라면
val = val * 10 + int(char) #숫자를 다루고 있다는 것을 알리고, # 원래 val의 자리수를 10 올리고 char을 정수형으로 더한다.
valProcessing = True
else: #char가 숫자가 아닐때,
if valProcessing == True: #전에 숫자 계산중었다면,
tokens.append(val) #tokens에 val 추가하고
val = 0 #val 초기화
valProcessing = False #현재 숫자 계산중이 아니므로 false
tokens.append(char) #문자열을 token에 더한다.
if valProcessing:
tokens.append(val)
return tokens
2.✏️ Postfix 계산하기
주의점
❗️
1.입력된 수식은 왼쪽부터 읽어온다.
2.수식은 연산자의 우선순위에 따라 계산된다.
3.괄호 안의 수식이 먼저 계산되어야하고, 곱셉과 나눗셈이 덧셈,뺄셈보다 먼저 계산되어야한다.
예시1
Infix = 6+(3-2)*4
1.3-2
2.1*4
3.6+4
Postfix = 632-4*4+
예시2
Infix = 3*(2+5)*4
1.(2+5)
2.3*7
3.21*4
Outfix = 325+*4*
문제상황을 정리하면
- 피연산자의 출력 순서는 동일하다.
- 당장 연산되지 않는 연산자를 저장할 곳이 필요하다(opstack이라 가정.)
- ’(‘연산자는 출력값(outstack이라가정)에 표현되지 않는다.
- ’)’연산자는 ‘(‘가 나올때까지 있는 연산자를 출력하게끔한다.
- ”+-*/”연산자는 opstack에 아무런 연산자가 없는 경우, opstack에 추가되어 기다린다.
- opstack에 연산자가 존재한다면, 자기자신보다 같거나 높은 우선순위의 연산자들을 차례로 outstack에 추가한후, 자기자신을 opstack에 추가한다.
- 연산이 종료된 뒤, opstack에 연산자가 남아있다면, outstack에 추가한다.
좀 어려울수도 있다.
이를 코드로 나타내 이해해보자.
def infix_postfix(token_list):
prio = {
"*" : 3,
"/" : 3,
"+" : 2,
"-" : 2,
"(" : 1
}
opstack = stack()
outstack_rs = []
for token in token_list:
if type(token) is int: #만약 정수라면 outstack에 추가.
outstack_rs.append(token)
elif token == "(": #만약 (라면 opstack에 추가한다.
opstack.push(token)
elif token == ')': #만약 )라면
while opstack.top() != '(': #(가 나올때까지 outstack_rs에 opstack을 추가한다.
outstack_rs.append(opstack.pop())
opstack.pop()
else: #연산자라면
if opstack.isEmpty(): # opstack이 비어있을때는 push
opstack.push(token)
else: #opstack이 비어있지 않다면
while len(opstack) > 0: #opstack이 있을 경우에만 반복한다.
if prio[opstack.top()] >= prio[token]: #opstack의 top이 token의 우선순위보다 높거나 같을때만
outstack_rs.append(opstack.pop()) #opstack을 꺼내서 outstack_rs에 추가한다.
else:
break
opstack.push(token) #우선순위가 같거나 높은 연산자들을 빼낸 후에는 현재 token을 추가한다.
while not opstack.isEmpty(): #opstack이 남아있다면, 나머지 처리.
outstack_rs.append(opstack.pop())
return outstack_rs
3.✏️ Calculation
Postfix 를 계산해 값을 도출해내야 한다.
예시
3+3 = 33+
3*3+3 = 33*3+
3*(2+5)*4 = 325+*4*
6+(3-2)*4 = 632-4*4+
문제상황
- 연산자가 나타나면 앞의 두 피연산자를 연산한다.
- 연산값은 다시 스택에 넣어 다음 연산도 바로 할 수 있어야한다.
이를 코드로 나타내면
def compute(token_list):
intstack = stack() #연산자를 넣고, 연산값을 계산해 넣을 스택
for token in token_list:
if type(token) == int: #만약 정수라면 스택 push
intstack.push(token)
elif token == '*': #각 연산자에 맞게 분기하고, 스택의 마지막 2개 값을 pop해 연산후 스택에 push
intstack_n2 = intstack.pop()
intstack_n1 = intstack.pop()
intstack.push(intstack_n1 * intstack_n2)
elif token == '/':
intstack_n2 = intstack.pop()
intstack_n1 = intstack.pop()
intstack.push(int(intstack_n1 / intstack_n2))
elif token == '+':
intstack_n2 = intstack.pop()
intstack_n1 = intstack.pop()
intstack.push(intstack_n1 + intstack_n2)
elif token == '-':
intstack_n2 = intstack.pop()
intstack_n1 = intstack.pop()
intstack.push(intstack_n1 - intstack_n2)
return intstack.pop()
참고자료
개인적인 공부를 위한 글이며, 모든 저작권은 신천수 교수님께 있습니다.
자세한 강의 내용은 신천수 교수님 강의를 참고하시면 좋을 것 같습니다.
😇 신천수 교수님 자료구조 강의
infix-postfix 코드는 이분 코드를 참고했습니다.
댓글남기기