[알고리즘 강의] 파트13. 스택의 응용: 후위 표기 수식 계산

중위 표기법과 후위 표기법

중위 표기법 (infix notation) - 연산자가 피연산자들의 사이에 위치

(A + B) * (C + D)

 

후위 표기법 (postfix notation) - 연산자가 피연산자들의 뒤에 위치

A B + C D + *

 

후위 표기식의 계산

알고리즘의 설계

후위 표현식을 왼쪽부터 한 글자씩 읽어서

    피연산자이면 스택에 push

    연산자를 만나면 스택에서 pop -> (1), 또 pop -> (2)

        (2) 연산 (1) 을 계산, 이 결과를 스택에 push

 

수식의 끝에 도달하면 스택에서 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 token in tokenList:
        if type(token) is int:
            postfixList.append(token)
        elif token == '(':
            opStack.push(token)
        elif token == ')':
            while not opStack.isEmpty():
                pop_token = opStack.pop()
                if pop_token == '(':
                    break
                postfixList.append(pop_token)
        else:
            while not opStack.isEmpty():
                if prec[opStack.peek()] >= prec[token]:
                    postfixList.append(opStack.pop())
                else:
                    break
            opStack.push(token)
            
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())

    return postfixList


def postfixEval(tokenList):
    valStack = ArrayStack()
    
    for token in tokenList:
        if type(token) is int:
            valStack.push(token)
            continue
        
        token1 = valStack.pop()
        token2 = valStack.pop()
        
        if token == '+':
            valStack.push(token2 + token1)
        elif token == '-':
            valStack.push(token2 - token1)
        elif token == '*':
            valStack.push(token2 * token1)
        elif token == '/':
            valStack.push(token2 / token1)
    
    return valStack.pop()
        


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

 

* 프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?' 강의를 듣고 정리하였습니다.