(Python/Stack) 후위 표식 계산

문제 출처: 어서와 자료구조와 알고리즘은 처음이지?

 

풀이:

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 i in tokenList:
        if type(i) == int:
            postfixList.append(i)
        elif i == '(':
            opStack.push(i)
        elif i == ')':
            while opStack.peek() != '(':
                postfixList.append(opStack.pop())
            opStack.pop()
        else:
            if opStack.isEmpty():
                opStack.push(i)
            else:
                while opStack.size() >= 0:
                    if prec[opStack.peek()] >= prec[i]:
                        postfixList.append(opStack.pop())
                    else:
                        break
                opStack.push(i)
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    return postfixList

def postfixEval(tokenList):
    num = ArrayStack()

    for i in tokenList:
        if type(i) == int:
            num.push(i)
        else:
            A = str(num.pop())
            B = str(num.pop())
            num.push(eval(B+i+A))
    return num.pop()

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

내가 구현해야하는것은

 

infixToPostfix 

postfixEval

 

1.1) infixToPostfix 

 

def infixToPostfix(tokenList):
    prec = {
        '*': 3,
        '/': 3,
        '+': 2,
        '-': 2,
        '(': 1,
    }
    opStack = ArrayStack()
    postfixList = []
    for i in tokenList:
        if type(i) == int:
            postfixList.append(i)
        elif i == '(':
            opStack.push(i)
        elif i == ')':
            while opStack.peek() != '(':
                postfixList.append(opStack.pop())
            opStack.pop()
        elif i in prec :
            if opStack.isEmpty():
                opStack.push(i)
            else:
                while opStack.size() > 0:
                    if prec[opStack.peek()] >= prec[i]:
                        postfixList.append(opStack.pop())
                    else:
                        break
                opStack.push(i)
        else:
            postfixList += i
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    return postfixList

 

이 전 문제와 동일하다.

 

 

 

def postfixEval(tokenList):
    num = ArrayStack()
    for i in tokenList:
        if type(i) == int:
            num.push(i)
        else:
            A = str(num.pop())
            B = str(num.pop())
            num.push(eval(B+i+A))
    return num.pop()

 

eval 함수를 사용한다 

eval 함수란 만약 '3 + 5' 문자열 형식으로 들어있는 것을 계산해서 리턴해준다 

위 코드로 하면

 

A 는 3이고 B 가 5일때 사칙 연산을 하고 싶을때

elif 를사용하여 '+' 일때 '-' 일때 하나하나씩 해도 되지만

else로 받은 int형 을 문자열로 바꿔주고 i 가 '+-*/'  중 하나 이고 '/'  '-' 일때 pop은 맨 위에서 부터 하므로 B,A 순서를 바꿔주고

그리고 다시 num에 넣어준다.