수식의 후위 표기법(Postfix Notation)

일상적으로 사용하는 중위 표기법(infix notation)이 아닌 후위 표기법(postfix notation)으로 수식을 계산하는 알고리즘
여기서는 연산자와 소괄호만을 고려하였음

참고 : 배열을 통해 구현한 스택(ArrayStack) yj-computer.tistory.com/111?category=926838

splitTokens() : string 타입으로 받은 수식을 list 타입으로 바꾸는 함수

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

---

infixToPostfix() : infix를 postfix로 변환
1. 피연산자는 list에 추가
2. 여는 괄호는 push
3. 닫는 괄호는 여는 괄호가 나올 때 까지 pop해서 list에 추가. 여는 괄호는 pop
4. 연산자의 우선순위가 peek 연산자 우선순위보다 낮으면 push, 높거나 같으면 pop하고 push
5. 스택에 남은 값 list에 추가

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 == ')':  # 여는 괄호가 나올 때까지 opStack의 원소 pop해서 list에 저장
            while opStack.peek() != '(':
                postfixList.append(opStack.pop())
            opStack.pop()   # 여는 괄호 pop
        else: # token is operator
            if not opStack.isEmpty():
                # 스택이 비어있지 않고 스택의 맨 위에 있는 연산자의 우선 순위가 더 높거나 같을 때
                while not opStack.isEmpty() and prec[opStack.peek()] >= prec[token]:
                    postfixList.append(opStack.pop())
            opStack.push(token)
                    
    while not opStack.isEmpty(): # 남은 연산자 모두 pop해서 list에 저장
        postfixList.append(opStack.pop())
        
    return postfixList

---

postfixEval() : 후위 표기법 수식을 계산하는 함수
1. 수식을 왼쪽부터 차례로 읽음
2-1. 피연산자는 스택에 push
2-2-1. 연산자가 나오면 스택에서 피연산자 2개 pop해서 계산
2-2-2. 결과는 다시 push

def postfixEval(tokenList):
    operand = ArrayStack()
    
    for token in tokenList:
        if type(token) is int:
            operand.push(token)
        else: # token is operator
            a = operand.pop()
            b = operand.pop()
            # 먼저 들어간 값이 나중에 pop되므로
            # b operater a
            if token == '+':
                res = b+a
            elif token == '-':
                res = b-a
            elif token == '*':
                res = b*a
            else: # /
                res = b/a
            operand.push(res)
                
    return operand.pop()

실행 예

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

---

프로그래머스 - 어서와! 자료구조와 알고리즘은 처음이지? 강의를 듣고 정리한 내용
https://programmers.co.kr/learn/courses/57