파이썬) 후위 표기법 수식을 계산하기

중위 표기법은 연산자가 두개의 피연산자 사이에 있는 표기법이고, 후위 표기법은 연산자가 두개의 피연산자 뒤에 있는 표기법이다. 

 

후위 표기법으로 되어있는 식을 스택을 이용해 계산하는 방법은 다음과 같다. 

 

ex) AB+CD+*

 

1.

식을 왼쪽부터 한글자씩 읽어나가는 방식으로 우선 피연산자는 스택에 push한다. 

 

2.

연산자 +를 만나면 스택에 있는 두 피연산자를 pop한 후 계산을 한다. 그 뒤 계산된 값을 다시 스택에 push한다. 

 

3.

CD+부분도 위와 마찬가지 방식이고 A+B위에 push될 것이다. 마지막 연산자 *를 만났는데 마찬가지 방식으로 C+D와 A+B를 pop한 후 계산한 뒤 스택에 푸쉬 한다.

 

4.

 

수식을 다 읽고 난 후 스택에 남아있는 값을 pop한 후 출력하면 원하는 계산값이 나온다. 

 

 

위 방법을 총 정리하면 후위 표현식을 왼쪽부터 한 글자씩 읽어서

 

• 피연산자이면 스택에 push
• 연산자를 만나면 스택에서 pop한 후 또 한번 pop을 한다. 먼저 pop된 것부터 a,b라 지정하면 연산 결과 (b 연산자 a)를 스택에 push한다.

수식을 다 읽고 난 후 스택에 남아 있는 값을 pop하면 원하는 계산 결과가 나온다.

 

후위 표기식을 계산하는 코드는 다음과 같다.

def postfixEval(tokenList):
    valStack=ArrayStack()
    
    for s in tokenList:
        if s=='*':  # 연산자인 경우
            a=valStack.pop()
            b=valStack.pop()
            c=b*a
            valStack.push(c)
        elif s=='/':
            a=valStack.pop()
            b=valStack.pop()
            c=b/a
            valStack.push(c)
        elif s=='+':
            a=valStack.pop()
            b=valStack.pop()
            c=b+a
            valStack.push(c)
        elif s=='-':
            a=valStack.pop()
            b=valStack.pop()
            c=b-a
            valStack.push(c)
        else :  #피연산자이면 스택에 push
            valStack.push(s)
            
    answer= valStack.pop()   # 수식의 끝에 도달하면 스택에서 pop
    return answer

 

s가 연산자인 경우 네가지 경우가 따로 작성이 되는데 그 이유는 연산자와 두 피연산자의 연산 결과를 스택에 push해야하기 때문에 각각의 연산 경우에 맞게 작성을 해야하기 때문이다.

 

위 코드는 필자가 작성한 것이기 때문에 효율적인 답이 아닐 수 있습니다