Python으로 알고리즘 공부 07. 중위표기법(Infix)를 후위표기법(Postfix)로 변환

Infix를 Postfix로 바꾸기

중위 표기법(Infix)

• 우리가 흔히 아는 산술식이다.

• 2 + 3 * 4 혹은 2 + 5 * ( 3 + 4 ) 등과 같이 괄호나 우선순위에 의해 풀어가는 방식.

• 인간이 계산하기에 친숙한 표기법이다.

후위 표기법(Postfix)

• 반면 컴퓨터는 중위표기법으로 계산을 하는 건 매우 어려운 문제이기 때문에 이를 보완하기 위해 후위 표기법으로 바꿔준다.

• 2 3 4 * + 혹은 2 5 3 4 + * + 등으로 표기한다.

• 연산자가 나오면 그 이전의 숫자 2개와 연산을 하는 방식이다.

• 2 3 4 * +는 2 12 +으로, 그리고 14 순으로 계산한다.

Infix를 Postfix로

• 중위 표기법을 후위 표기법으로 바꾸기 위해서는 스택을 이용한다.

1. infix를 순서대로 읽는다.

2. 읽은 값이 여는 괄호 '('이면, 스택에 넣는다.

3. 읽은 값이 닫는 괄호 ')'이면, 스택에서 여는 괄호가 나올 때까지 pop을 수행하여 postfix에 출력한다.

4. 읽은 값이 숫자이면, postfix에 출력한다.

5. 읽은 값이 연산자이면, 스택에서 자기보다 낮은 연산자를 꺼내 postfix에 출력한다.

6. 마지막으로 스택에 남아있는 것을 순서대로 pop하여 postfix에 출력한다.

Python 예제

#infix = [ '2', '*', '(', '5', '+', '7', ')', '+', '8']
infix = [ '2', '+', '3', '*', '4']
postfix = []
stack = []
operator = ['*', '/', '+', '-']
bracket = ['(', ')']
​
def is_number(x):
    if x not in operator and x not in bracket:
        return True
    else:
        return False
    
def pref(x):
    if x is '*' or x is '/':
        return 1
    elif x is '+' or x is '-':
        return 0
​
for c in infix:
    if is_number(c):
        postfix.append(c)
    elif c in operator:
        p = pref(c)
        while len(stack) > 0:
            top = stack[-1]
            if pref(top) <= p:
                break
            postfix.append(stack.pop())            
        stack.append(c)
        
    elif c == '(':
        stack.append(c)
    elif c == ')':
        while True:
            x = stack.pop()
            if x == '(':
                break
            postfix.append(x)
            
while len(stack) > 0:
    postfix.append(stack.pop())