12강: 수식의 후위 표기

강의

중위 표기법 (infix notation) : 연산자가 피연산자들의 사이에 위치

후위 표기법 (postfix notation) : 연산자가 피연산자들의 뒤에 위치

 

알고리즘 설계

1. 연산자의 우선순위 설정

2. 왼쪽부터 한 글자씩 읽기

3. 열린 괄호는 push, 닫힌 괄호는 열린 괄호가 나올 때까지 pop

4. 수식을 끝까지 확인한 후 스택에 남은 연산자 모두 pop

 

 

12강 실습: 중위표현 수식 --> 후위표현 수식

⭐ 힌트 : 스택에서 꺼내지 않고 peek()를 이용해 우선순위 비교하고 isEmpty() 이용하여 모두 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]

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

def solution(S):
    opstack = ArrayStack()
        
    ans = ""
    
    for s in S:        
        if s == "(":
            opstack.push(s)
            
        elif s in prec:
            while not opstack.isEmpty() and prec[s] <= prec[opstack.peek()]:
                ans += opstack.pop()
            opstack.push(s)

        elif s == ")":
            while opstack.peek() != "(":
                ans += opstack.pop()
            
            opstack.pop()
            
        else:
            ans += s
            
    while not opstack.isEmpty():
        ans += opstack.pop()
        
    return ans