python - 스택 후위표기법을 중위표기법으로 변경

 

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)

    print(tokens)
    return tokens

#중위 -> 후위
def infixToPostfix(tokenList):
    prec = {
        '*': 3,
        '/': 3,
        '+': 2,
        '-': 2,
        '(': 1,
    }

    opStack = ArrayStack()
    p_fixList = []
    
    for v in tokenList :
        if type(v) is int :
            p_fixList.append(v)
        elif v == '(' :
            opStack.push(v)
        elif v == ')' :
            while opStack.peek() != '(' :
                p_fixList.append(opStack.pop())
            opStack.pop()
        else :
            if v in prec :
                if opStack.isEmpty() :
                    opStack.push(v)
                else :
                    while prec.get(v) <= prec.get(opStack.peek()) :
                        p_fixList.append(opStack.pop())
                        if opStack.isEmpty() : break
                    opStack.push(v)

            
    while not opStack.isEmpty() :
        p_fixList.append(opStack.pop())

    return p_fixList

#후위 -> 중위 계산
def postfixEval(tokenList):
    result = 0
    valStack = ArrayStack()
    
    for val in tokenList :
        if type(val) is int :
            valStack.push(val)
        else :
            n2 = valStack.pop()
            n1 = valStack.pop()

            if val == '*' :
                valStack.push(n1 * n2)
            elif val == '/' :
                valStack.push(n1 / n2)
            elif val == '+' :
                valStack.push(n1 + n2)
            elif val == '-' :
                valStack.push(n1 - n2)
                    
    result = valStack.pop()
    
    return result


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

 

 

후위 -> 중위 변경 (계산은 2개씩하는것으로 가정)

 

1. 

읽을 때마다 stack에 비계산법 문자를 push하고 계산법이 읽히면 (*/+-) stack에서 2개씩 pop해서 계산 후

계산값 다시 stack에 push한다.

 

2. 

반복 후 문자열 모두 읽으면, stack에 있는 계산이 완료 된 값을 pop한다.