Expression evaluation
파이썬 자료구조를 활용해서 수식을 계산해보자!
수식에는 + - * / 와 같은 연산자와 1 2 3 a b c와 같은 피연산자가 있다.
수식 = {연산자 operator} + {피연산자 operand}
이때 연산자는 산술 연산자(+ - / *), 논리 연산자(and or), 할당 연산자(=) 등이 있다.
수식을 표현하는 방식은 연산자의 위치에 따라
infix, postfix, prefix로 분류할 수 있다.
- infix notation
주로 사람이 쓰는 수식 표현 방식이다.
a / b - c + d * e - a * c
- postfix notation
컴퓨터가 이해하기 위한 수식 표현 방식으로 연산자가 계산의 대상이 되는 피연산자 바로 뒤에 위치한다.
infix notation과 같은 수식을 postfix에서는
a b / c d e + a c * - 와 같이 표기한다.
- prefix notation
prefix notation은 연산자가 계산의 대상이 되는 피연산자 바로 앞에 위치하는 것이다.
prefix notation은 같은 수식을
- + - / a b c * d e * a c 와 같이 표기한다.
어떤 원리로 같은 수식을 이렇게 달리 표기하는 것인지 좀더 살펴보도록 하자.
infix notation
infix notation은 기본적으로 사람이 사용하는 방식이다.
연산자에는 우선순위가 부여되어 있다. + - 보다 / *의 우선순위가 높은 식이다.
그리고 우선순위를 조정하기 위해 괄호 ( )가 사용된다.
a * ( b + c ) + d / e - a / ( c * d ) 라는 수식을 괄호 친 굵은 글씨 부분부터 계산해주듯이, infix notation은 어느 곳에서나 계산이 시작될 수 있다.
postfix notation
그러나 infix notation은 계산 위치 / 우선순위를 판단해야한다는 점에서 컴파일러가 이해하기 어렵다.
그리하여 만들어진 표기법이 postfix notation이다.
postfix notation에는 우선순위, 괄호가 없고
그저 좌에서 우로 하나씩 계산하면 된다.
좌에서 우로 계산해주는 원리를 가지고 있기 때문에, First In First Out 원리로 작동하는 stack을 이용하여 계산해줄 수 있다.
6 2 / 3 - 4 2 * +이라는 postfix 수식을 예로 들어보자.
이 수식은 기본적으로 좌에서 우 방향으로 하나씩 저장한다. (6 -> 2 -> / -> 3 -> - -> 4 -> 2 -> * -> +)
만약에 이번 차례의 token이
=> 피연산자(6, 2, 3, 4, 2)라면, 스택에 하나씩 넣어둔다(push)
=> 연산자(- / * +)라면,
[1] 스택에서 피연산자 2개를 꺼내(pop)
[2] 둘을 연산자로 계산해주고
[3] 그 값을 다시 스택에 넣는다(push)
이를 반복하면서 postfix를 계산해주고, 수식의 끝에 도달하면 연산을 멈추는 것이 postfix evaluation의 원리이다.
이번에는 python으로 postfix evaluation을 구현해보자.
postfix evaluation으로 기대하는 입출력은 다음과 같다.
입력수식 : 57*43-6/9%+
5 [5]
7 [5, 7]
* [35]
4 [35, 4]
3 [35, 4, 3] - [35, 1]
6 [35, 1, 6]
/ [35, 0]
9 [35, 0, 9]
% [35, 0]
+ [35]
결과값 = 35스켈레톤 코드는 다음과 같다
# postfix evaluation
class Sym():
pass
class Expression:
def __init__(self):
pass
def eval_postfix(self):
pass
def getSymtype(self, sym):
pass
e = Expression()
print("입력수식 : ", e.expr)
print()
print("결과 = ", e.eval_postfix())
구현 코드
예제 코드에서는 class Sym()을 이용하여 self.expr를 분류하였으나,
나는 그러지 않고 eval_postfix 함수 안에서 판별하였다.
class Expression:
def __init__(self):
self.expr = '57*43-6/9%+'
self.len = len(self.expr)
self.stack = []
self.sym = None
def eval_postfix(self):
for i in range(self.len):
print(self.expr[i], end = ' ')
if self.getSymtype(self.expr[i]) == 'operand':
self.stack.append(int(self.expr[i]))
else:
op1 = self.stack.pop()
op2 = self.stack.pop()
if self.expr[i] == '+':
self.stack.append(op1 + op2)
elif self.expr[i] == '-':
self.stack.append(op2 - op1)
elif self.expr[i] == '/':
self.stack.append(op2 // op1)
elif self.expr[i] == '*':
self.stack.append(op1 * op2)
elif self.expr[i] == '%':
self.stack.append(op2 % op1)
print(self.stack)
return self.stack[0]
def getSymtype(self, sym):
self.sym = sym
if self.sym.isdigit():
return 'operand'
else:
pass
e = Expression()
print("입력수식 : ", e.expr)
print()
print("결과 = ", e.eval_postfix())infix to postfix conversion
이렇게 postfix 수식을 계산하는 방법을 구현해보았다.
이번에는 사람이 이해하는 수식(infix)을 입력값으로 받았을 때,
[1] postfix로 변환하여
[2] postfix 계산을 수행하는 것을 구현해보도록 하자.
- manual method
교과서적인 방법부터 시도해보자.
step 1. 우선순위에 따라 () 괄호 쳐주기
step 2. 괄호 안에서 연산자를 뒤로 옮기기 => 우괄호 삭제
step 3. 모든 수준의 괄호에 대하여 반복한 뒤에 괄호를 모두 삭제
예를 통해 보자면, 아래와 같은 기본 infix 수식 표현이 있다고 하자.
a / b - c + d * e - a * c이 수식에 우선순위에 따라 모든 괄호를 쳐주면, 맨 마지막줄처럼 된다.
이때 우선순위는 [1] * / 가 - +보다 높다 [2] 우선순위가 같을 경우, 앞에서부터 계산한다를 기준으로 삼았다.
(a / b) - c + (d * e) - (a * c)
((a / b) - c) + (d * e) - (a * c)
(((a / b) - c) + (d * e)) - (a * c)
((((a / b) - c) + (d * e)) - (a * c))
괄호 안에서 연산자를 뒤로 옮기면서 우괄호를 없애주는 것을
모든 우괄호가 사라질 때까지 반복한다
((((a / b) - c) + (d * e)) - (a * c))
((((a b / - c) + (d e *) - (a c *)
((((a b / c - (d e * + a c * -
a b / c - d e * + a c * -짠 완성~
이렇게 postfix 변환이 완성되었으나, 괄호를 치고 제거하는 과정이 번거롭기 때문에
실제로는 보다 효율적인 방법(한번만 훑고 지나가는 방법)을 사용한다.
이름하여..
- Algorithm for Single scan conversion
원칙 1. 피연산자는 그대로 출력값에 추가한다.
원칙 2. 연산자는 일단 stack에 push하고,
원칙 3. push한 tmp 연산자와 top 연산자의 연산자 우선순위를 비교하여 pop 해준다.
연산자 우선순위 비교 case
- tmp의 우선순위가 높다 ( tmp > top or empty stack )
- tmp의 우선순위가 낮거나 같다 ( tmp <= top)
- tmp가 수식의 끝이다 (eos)
각 경우에 어떻게 조치해주어야하는지 감을 잡기 위해 예시를 가져와보았다.
a + b * ctmp = a
=> operand이므로 pass
=> result = a, stack = []
tmp = +
=> operator이다.
=> empty stack이므로 일단 push
=> result = a, stack = [+]
tmp = b
=> operand이므로 pass
=> result = ab, stack = [+]
tmp = *
=> operator이다.
=> tmp가 stack의 top보다 우선순위가 높으므로 일단 push
=> result = ab, stack = [*, +]
tmp = c
=> operand이므로 pass
=> result = abc, stack = [*, +]
남아있는 stack의 연산자들을 하나씩 pop해주어 result에 더한다.
result = abc*+
- advanced : 괄호가 있는 수식의 경우 어떻게 처리하는가?
원칙 : 괄호 내부를 sub expression과 같이 처리한다.
원칙 1. 피연산자는 그대로 출력값에 추가한다.
원칙 2. 연산자는 일단 stack에 push하고,
원칙 3. push한 tmp 연산자와 top 연산자의 연산자 우선순위를 비교하여 pop 해준다.
연산자 우선순위 비교 case
- tmp의 우선순위가 높다 ( tmp > top or empty stack )
- tmp의 우선순위가 낮거나 같다 ( tmp <= top)
- tmp가 수식의 끝이다 (eos)
여기에 더하여 만약에
- tmp가 '('라면, 일단 push한다.
- tmp가 ')'라면, '('에 도착할 때까지 pop하고, '('는 출력하지 않는다.
- tmp가 eos(End Of String)이라면, pop하고, 모든 연산자를 출력한다.
- 셋 다 아닌 중간의 tmp에 대해서는,
=> - empty stack이거나 T의 우선순위가 top보다 높으면, push한다.
=> - T의 우선순위가 top보다 같거나 낮으면, pop(top)하고, 다시 push(tmp)한다.
infix를 postfix로 변환하는 것을 python으로 구현해보자
원하는 실행 결과는 다음과 같다.
e = Expression()
e.infix_postfix(expr)
<실행결과>
수식 : 9/(3+6-5)*7*(6-4)
9 []
/ ['/']
( ['/', '(']
3 + ['/', '(', '+']
6 - ['/', '(', '-']
5 ) * ['*']
7 * ['*']
( ['*', '(']
6 - ['*', '(', '-']
4 )
결과수식 936+5-/7*64-*구현 결과 (구현 중..)
class Expression:
def __init__(self):
self.expr = '57*43-6/9%+'
self.len = len(self.expr)
self.stack = []
self.expression = ''
self.sym = None
def eval_postfix(self):
for i in range(self.len):
print(self.expr[i], end = ' ')
if self.getSymtype(self.expr[i]) == 'operand':
self.stack.append(int(self.expr[i]))
else:
op1 = self.stack.pop()
op2 = self.stack.pop()
if self.expr[i] == '+':
self.stack.append(op1 + op2)
elif self.expr[i] == '-':
self.stack.append(op2 - op1)
elif self.expr[i] == '/':
self.stack.append(op2 // op1)
elif self.expr[i] == '*':
self.stack.append(op1 * op2)
elif self.expr[i] == '%':
self.stack.append(op2 % op1)
print(self.stack)
return self.stack[0]
def getSymtype(self, sym):
self.sym = sym
if self.sym.isdigit():
return 'operand'
else:
pass
def infix_postfix(self, expr):
for token in expr:
print(token, end=' ')
if self.getSymtype(token) == 'operand':
self.expression += token
else:
if token == '(':
self.stack.insert(0,token)
elif token == ')':
pop = self.stack.pop()
while pop != '(':
self.expression += pop
elif len(self.stack)==0:
self.stack.insert(0,token)
else:
if self.precedence(token) > self.precedence(self.stack[0]):
self.stack.insert(0,token)
elif self.precedence(token) <= self.precedence(self.stack[0]):
self.expression += self.stack.pop()
self.stack.insert(0,token)
print(self.stack)
while len(self.stack) > 0:
self.expression += self.stack.pop()
print()
print(self.expression)
def precedence(self, op):
if op == '+' or op == '-':
return 0
elif op == '*' or op == '/':
return 1
expr = '9/(3+6-5)*7*(6-4)'
e = Expression()
e.infix_postfix(expr)'Computer Science > 자료구조' 카테고리의 다른 글
| 자료구조 7강 | Search 탐색 (순차, 이진, 해시, 보간) | 숙명여대 학점교류 (0) | 2021.12.29 |
|---|---|
| 자료구조 6강-2 | Linked List | 숙명여대 학점교류 (0) | 2021.12.29 |
| 자료구조 6장 | Linked List | 숙명여대 학점교류 (0) | 2021.12.27 |
| 자료구조 5-2장 | Linear Data Structure | 숙명여대 학점교류 (0) | 2021.12.27 |
| Simple Data Structure | Queue, Circular Queue, Stack, N Queens Problem, fraction, prime number, fibonacci, bowling game, binary search (0) | 2021.12.25 |