[자료구조] 수식의 후위 표기법 변환, 계산 - python

2020 카카오 하계 인턴 코딩테스트에서 처참한 결과를 보며 느낀점이 많다.

아직 기초를 한참 더 쌓아야 가능할 것같다고 생각하였다.

이번 시간엔 파이썬과 스택 구조를 활용하여

수식의 후위 표기, 계산에 대해 공부해보도록 하자.

---

1. 수식의 후위 표기법

후위 표기법을 이야기하기 전에 수식의 여러가지 표기법에 대해 짚고 넘어가야한다.

수식엔 다양한 표기법이 존재한다.

 

• 전위(prefix) 표기법 : 연산자 먼저 표시, 피연산자를 나중에 표시
  • * + A B - C D
• 중위(infix) 표기법 : 피연산자 사이에 연산자를 표기(일반적으로 사용)
  • (A + B) * (C - D)
• 후위(postfix) 표기법 : 피연산자를 먼저 표시, 연산자를 나중에 표시
  • A B + C D - *

3개 예제는 모두 같은 공식이다. 중위 표기법을 일반적으로 우리가 사용하지만

프로그래밍으로 괄호가 포함된 중위 표기 연산 수식을 계산하긴 힘들다.

 

컴퓨터 프로그래밍시 괄호표기가 필요없는 후위 표기법을 이용하여

다양한 수식을 계산하는 것이 속도가 빠르다.

 

*계산기나 컴퓨터 내부에선 원래 스택을 활용해 중위표기법을 후위표기법으로 변환하여 연산한다.

2. 중위 표기법 -> 후위 표기법 변환

후위 표기법을 연산하기 위해선 일반적인 중위 표기법을 후위 표기법으로 변환할 필요가 있다.

변환 방법은 다음과 같다.

 

1. 수식의 각 연산자에 대해 우선순위에 따라 괄호를 사용하여 다시 표현한다.
2. 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.
3. 괄호를 제거한다.
   
   

예제를 통해 살펴보자. 위 공식을 이용하여

• A * C + B(중위 표기법)를 후위 표기법으로 변환해보자.

1. 우선순위에 따라 괄호를 다시 표현하면 ((A * B) + C)
2. 각 연산자를 오른쪽 괄호 뒤로 이동시키면 ((A B) * C) +
3. 괄호제거하면 마무리, A B * C +
   
   
   

3. 후위 표기법 계산

이제는 후위 표기법을 계산해보자.

이제부터 스택 개념을 적용할 것이며 계산 방법은 다음과 같다.

*스택 : https://saynot.tistory.com/28

1. 처음부터 차례대로 읽으며 피연산자는 스택에 쌓는다.
2. 연산자를 만나면 스택에서 피연산자 2개를 꺼내 연산을 수행하고 다시 스택에 쌓는다.
3. 모두 읽을 때 까지 위 두 공식을 반복한다.

역시 예제를 통해 알아보자.

위 공식을 이용하여 13 5 + 3 -(후위 표현식) 수식을 계산해보자.

1. 13은 피연산자, 스택에 PUSH
2. 5는 피연산자, 스택에 PUSH
3. +는 연산자이므로 5 POP, 13 POP하여 연산 수행
4. 13 + 5 = 18, 결과값을 스택에 PUSH
5. 3은 피연산자, 스택에 PUSH
6. -는 연산자이므로 3 POP, 18 POP하여 연산 수행
7. 18 - 3 = 15, 계산 끝
8. 13 5 + 3 - = 15
   
   
   

4. 알고리즘 설계

중위 표현식 > 후위 표현식 변환 알고리즘

1. 연산자 우선순위 지정(이걸 바꾸는 코딩테스트 문제 존재)
2. 후위 표현식으로 만들어져 반환될 리스트 생성
3. 중위 표현식을 왼쪽부터 한 글짜씩 읽음
4. 피연산자면 리스트에 append
5. '('이면 스택에 PUSH, ')'이면 '('가 나올때까지 스택에서 POP, 리스트에 append
6. 연산자면 스택에서 이보다 높은 우선순위들 POP, 리스트에 append
7. 그리고 이 연산자를 스택에 PUSH
8. 스택에 남아있는 연산자는 모두 POP, 리스트에 append
   
   

후위 표현식 계산 알고리즘

1. 후위 표현식을 왼쪽부터 한 글짜씩 읽음
2. 피연산자면 스택에 PUSH
3. 연산자면 스택에서 POP해서 op1, 다시 POP해서 op2 지정
4. op2와 op1을 연산자로 계산하여, 결과값 스택에 PUSH
5. 수식의 끝이면 스택에서 POP하여 계산 결과 도출
   
   
   

4. 코딩 - Python

위 두가지를 이용하여 중위 표현식을 입력받으면 후위 표현식으로 변환하여

결과값을 도출하는 알고리즘을 구현해보았다.

*splitTokens함수와 Stack 클래스는 해당 주제에서 제외되는 부분이라 생략하였다.

def infixTopostfix(tokenList): #중위 표현식을 후위 표현식으로 변환
    prec = {
        '*': 3,
        '/': 3,
        '+': 2,
        '-': 2,
        '(': 1,
    }

    opStack = ArrayStack()
    postfixList = []

    for token in tokenList:
        if type(token) is int:
            postfixList.append(token)         
        elif token == ')':
            if token == ')':
                while opStack.peek() != '(':
                #print(opStack.peek())
                    postfixList.append(opStack.pop())
                opStack.pop()
        else:
            if opStack.isEmpty() == False:  
                if prec[opStack.peek()] >= prec[token] and token != '(':
                    postfixList.append(opStack.pop())
                    opStack.push(token)
                elif prec[opStack.peek()] >= prec[token] and token == '(':
                    opStack.push(token)
                else:
                    opStack.push(token)
            elif opStack.isEmpty() == True:
                opStack.push(token)

    while not opStack.isEmpty():
        postfixList.append(opStack.pop())

    return postfixList


def postfixEval(tokenList): #후위 표현식 계산
    opStack = ArrayStack()
    for token in tokenList:
        if type(token) is int:
            opStack.push(token)
        elif token == '*':
            tmp1 = opStack.pop()
            tmp2 = opStack.pop()
            opStack.push(tmp2*tmp1)
        elif token == '/':
            tmp1 = opStack.pop()
            tmp2 = opStack.pop()
            opStack.push(tmp2/tmp1)
        elif token == '+':
            tmp1 = opStack.pop()
            tmp2 = opStack.pop()
            opStack.push(tmp2+tmp1)
        elif token == '-':
            tmp1 = opStack.pop()
            tmp2 = opStack.pop()
            opStack.push(tmp2-tmp1)
    return opStack.pop()



def solution(expr):
    tokens = splitTokens(expr) #문자열을 토큰화 시키는 함수
    print("tokens : ", tokens)
    postfix = infixTopostfix(tokens) #중위 표현식 > 후위 표현식
    print("postfix : ", postfix)
    res = postfixEval(postfix) #후위 표현식 계산
    return res

def main():
    quest = '( 13 + 15 ) * ( 16 + 23 )'
    ans = solution(quest)
    print(quest, " = ",ans)

if __name__ == '__main__':
    main()

결과는 다음과 같다.

---

일반적으로 수식 순서는 * /가 + -에 비해 먼저이다. 하지만 이를 바꿔서 계산해야하는

코딩 테스트 문제가 존재한다. 이럴때 위 코드에서 사전을 수정하여 우선순위를 조절해 코드를 바꾸면 될것이다.