13강: 후위 표기 수식 계산

강의

알고리즘 설계

1. 왼쪽부터 한 글자씩 읽기

2. 피연산자이면 push, 연산자면 pop

 

 

13강 실습: 후위표현 수식 계산

⭐ 계산한 값을 다시 push해서 마지막까지 valStack에 값이 남도록 하는 문제!

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 s in tokenList:        
        if s == "(":
            opStack.push(s)
            
        elif s in prec:
            while not opStack.isEmpty() and prec[s] <= prec[opStack.peek()]:
                postfixList.append(opStack.pop())
            opStack.push(s)

        elif s == ")":
            while opStack.peek() != "(":
                postfixList.append(opStack.pop())
            
            opStack.pop()
            
        else:
            postfixList.append(s)
            
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
        
    return postfixList


def postfixEval(tokenList):
    valStack = ArrayStack()
    
    for t in tokenList:
        if type(t) is int:
            valStack.push(t)
        
        else:
            if t == "*":
                a = valStack.pop()
                b = valStack.pop()
                valStack.push(b * a)
            elif t == "/":
                a = valStack.pop()
                b = valStack.pop()
                valStack.push(b / a)
            elif t == "+":
                a = valStack.pop()
                b = valStack.pop()
                valStack.push(b + a)
            elif t == "-":
                a = valStack.pop()
                b = valStack.pop()
                valStack.push(b - a)
                
    return valStack.pop()

def solution(expr):
    tokens = splitTokens(expr)
    postfix = infixToPostfix(tokens)    # 중위 -> 후위
    val = postfixEval(postfix)
    return val