13강: 후위 표기 수식 계산

유태형·2022년 3월 9일

알고리즘 - Python

목록 보기

9/16

13강 요약

후위연산은 중위연산과 다르게 괄호가 필요없고 좌측부터 순서대로 2개의 피연산자와 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

val을 주의해서 봐야한다 문자열로 숫자가 여러개 이어져있다고 가정하자. 가령 '123 + 100'을 요소들로 뽑아냈을때 1 2 3 + 1 0 0들로 이루어진것이 아니라 123 + 100으로 정수의 자리수를 고려하여야 한다.

val은 자리수를 고려하여 숫자들이 연속으로 나올때 * 10과 +현재수를 하여 정수가 되도록 값을 저장한다.

valProcessing은 val에 연속적인 숫자가 들어올때와 아닐때를 구분시켜 플래그 역할을 수행한다.

중위연산자를 후위연산자로 전환

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 opStack.peek() != '(': #괄호 나올때까지
                postfixList.append(opStack.pop()) #pop
            opStack.pop() #괄호도 삭제
        else:
            if opStack.isEmpty():
                opStack.push(token)
            else:
                while opStack.isEmpty() == False and prec[opStack.peek()] >= prec[token]:
                    postfixList.append(opStack.pop())
                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)
        elif token == '*':
            num2 = valStack.pop()
            num1 = valStack.pop()
            valStack.push(num1 * num2)
        elif token == '/':
            num2 = valStack.pop()
            num1 = valStack.pop()
            valStack.push(num1 / num2)
        elif token == '+':
            num2 = valStack.pop()
            num1 = valStack.pop()
            valStack.push(num1 + num2)
        elif token == '-':
            num2 = valStack.pop()
            num1 = valStack.pop()
            valStack.push(num1 - num2)
    
    return valStack.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 opStack.peek() != '(': #괄호 나올때까지
                postfixList.append(opStack.pop()) #pop
            opStack.pop() #괄호도 삭제
        else:
            if opStack.isEmpty():
                opStack.push(token)
            else:
                while opStack.isEmpty() == False and prec[opStack.peek()] >= prec[token]:
                    postfixList.append(opStack.pop())
                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)
        elif token == '*':
            num2 = valStack.pop()
            num1 = valStack.pop()
            valStack.push(num1 * num2)
        elif token == '/':
            num2 = valStack.pop()
            num1 = valStack.pop()
            valStack.push(num1 / num2)
        elif token == '+':
            num2 = valStack.pop()
            num1 = valStack.pop()
            valStack.push(num1 + num2)
        elif token == '-':
            num2 = valStack.pop()
            num1 = valStack.pop()
            valStack.push(num1 - num2)
    
    return valStack.pop()


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