[자료구조] 중위 표현 수식 -> 후위 표현 수식 스택 파이썬

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]

prec = {
    '*': 3, '/': 3,
    '+': 2, '-': 2,
    '(': 1
}

def solution(s):
    opStack = ArrayStack()
    answer = ""
    for op in s:
        # 닫는 괄호를 만나는 경우
        if op == ")":
            #  여는 괄호를 만날 때까지 pop
            while opStack.peek() != "(":
                answer += opStack.pop()
            # 스택에 있는 여는 괄호 pop
            opStack.pop()
        # 연산자들이 아닌 경우
        elif op not in prec:
            answer += op
        else:
            # 스택이 비어있는 경우
            if opStack.isEmpty():
                opStack.push(op)
            # 스택에 연산자들이 있는 경우
            else:
                # 현재의 연산자의 우선 순위가 더 큰 경우
                if prec[opStack.peek()] < prec[op] or op == "(":
                    opStack.push(op)
                # 현재의 연산자의 우선 순위가 더 작은 경우
                else:
                    # 스택에 있는 연산자들 중 현재의 연산자보다 우선 순위가 더 큰 경우 모두 pop
                    while not opStack.isEmpty():
                        if prec[opStack.peek()] >= prec[op]:
                            answer += opStack.pop()
                        else:
                            break
                    opStack.push(op)
    while not opStack.isEmpty():
        answer += opStack.pop()

    return answer

출처: airvw.github.io/datastructure/2020-12-07-prefix-to-postfix/

스택 문제에서 매번 틀리는 부분:

스택이 비었을때 채워주기

 

큰 분기가 무엇인지 항상 생각하기