후위 표기 수식 계산

후위 표기 수식 계산

• 이전 강의에서는 중위표현식을 후위 표기식으로 전환하는 알고리즘을 학습했다.
• 이제는 전환된 후위 표기식을 스택을 이용해 계산해보자.
• 스택 기반 후위 표기식을 이용하여 계산 효율성을 높일 수 있다는 것을 이해해보자.

후위 표기식의 계산

쉽게 생각해서 피연산자를 순차적으로 스택에 넣은 다음 연산자를 만날 경우 해당 피연산자를 연산하면 된다.

계산 알고리즘 순서

1. 수식을 왼쪽부터 차례대로 스캔한다
2. 피연산자가 나타나면, 스택에 넣어 둔다.
3. 연산자가 나타나면 , 스택에 들어 있는 피연산자를 두 개 꺼내어 연산한다.
4. 그 결과를 스택에 다시 넣어 둔다.
5. 스캔이 끝나면 가장 마지막 값을 pop한다.
   
   

실습

 

class ArrayStack:

    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]


def splitTokens(exprStr):
    tokens = []
    val = 0
    valProcessing = False
    for c in exprStr:
        if c == ' ':
            continue
        if c in '0123456789':
            val = val * 10 + int(c)
            valProcessing = True
        else:
            if valProcessing:
                tokens.append(val)
                val = 0
            valProcessing = False
            tokens.append(c)
    if valProcessing:
        tokens.append(val)
    return tokens


def infixToPostfix(tokenList):
    prec = {
        '*': 3,
        '/': 3,
        '+': 2,
        '-': 2,
        '(': 1,
    }

    opStack = ArrayStack()
    postfixList = []
    
    for w in tokenList:
        "13 * 27 + 36 * 34"
        if(w == ")"):
             for _ in range(0,opStack.size()):
                if(opStack.peek() != "("):
                    pop_w = opStack.pop()
                    postfixList.append(pop_w)
                else:
                    break  
        
        elif w not in prec: 
            postfixList.append(w)
        else:
            if(opStack.size() == 0):
                opStack.push(w)
                continue
                
            elif(w == "("):
                opStack.push(w)
                continue
        
            elif (prec[opStack.peek()] >= prec[w]):
                for _ in range(0,opStack.size()):
                    pop_w = opStack.pop()
                    if(pop_w != "("):
                        postfixList.append(pop_w)
            
            opStack.push(w) 
            
              
                
    if opStack.size() != 0 :
        for w in range(0,opStack.size()):
            pop_w = opStack.pop()
            if(pop_w != "("):
                postfixList.append(pop_w)
                              

    return postfixList


def cal(s, opt):
    
    s2 = s.pop()
    s1 = s.pop()
    
    if(opt == "+"):
        return s1 + s2
    
    if(opt == "-"):
        return s1 - s2
    
    if(opt == "*"):
        return s1 * s2
    
    if(opt == "/"):
        return s1 // s2
    
    
    


def postfixEval(tokenList):
    opStack = ArrayStack()
    
    for w in tokenList:
        if type(w) == int:
            opStack.push(w)
        else:
            
            new = cal(opStack,w)
            opStack.push(new)
            
                
    return opStack.peek()
    

def solution(expr):
    tokens = splitTokens(expr)
    postfix = infixToPostfix(tokens)
    val = postfixEval(postfix)
   
    return val

 

정리

두개의 피연산자를 꺼내 계산하는 부분을 추가로 구현하였다. 이 경우 "-" 또는 "/"가 연산자인 경우 꺼내는 순서를 제대로 지정해주어야한다.나는 postfix로 변환하는 것에 있어서 “(”를 우선순위와 상관없이 push해주는 부분을 생각하지 못해 조금 헤메었다.

 

postfixEval를 구현해보니 생각보다 쉽게 계산 결과를 구할 수 있었다. 후위연산자를 이용한 계산의 효율성을 사용하는 분야는 계산량이 많은 머신러닝이 아닐까? 아니면 대용량 로그 정보에 값을 후위연산자로 기록해놓아서 필요할 때만 통계를 만들어 낼 경우 사용할 것으로 보인다.

 

실제로 자동 미분(Autodiff) 기법을 사용하는 딥러닝 프레임워크(TensorFlow, PyTorch 등)에서는 수식의 계산 순서를 처리할 때 이와 비슷한 방식으로 그래프를 구축해 최적화된 연산을 수행한다고 한다.

또한 웹 서버나 애플리케이션에서 로그 분석을 할 때, 미리 수식을 중위 형태로 계산하지 않고, 후위 표기법으로 저장해 두었다가, 필요한 시점에서 빠르게 계산하여 트래픽 통계나 성능 분석을 할 수 있다.

• 이 방식은 실시간 계산보다는 저장해 두고 나중에 요구가 발생했을 때 효율적으로 계산할 수 있다는 장점있다.