[Programmers] 후위표현 수식

생각

손으로 스택을 직접 그려보면서 중위표현식이 어떻게 후위표현식으로 바뀌는지 생각하면 된다. 닫는 괄호 연산자 마무리 작업(pop연산)을 잊지 말자

설계

1. 알파벳이면 그냥 출력
2. '(' 이면 스택에 push
3. ')' 이면 '('이 나올때까지 스택에서 pop 출력하고 pop한 원소를 결과값에 추가한다. 이 과정이 끝나고나서 한번 더 pop을 해줘야 ')'를 제거해주자
4. 연산자가 나올때, 스택의 peek연산을 통해 연산자들끼리의 우선순위를 비교해준다. 그 다음 peek연산 결과값이 현재 연산자의 우선순위보다 크거나 같으면 스택에서 pop하고 결과값에 추가한다.
   (스택에 원소가 없거나 연산자 우선순위가 낮은것이 나올때까지 진행해야하는 조건을 통해 진행한다) 이 과정을 통해 연산자를 빼주고 반복문이 종료되면 현재 연산자를 스택에 push한다.
5. 1~4 과정을 문자열의 길이만큼 반복한뒤 스택에 남아있는 연산자를 모두 pop해서 결과값에 더해준다.

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]

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

def solution(S):
    stack = ArrayStack()
    answer = ''
    for c in S:
        if c not in '+-*/()':
            answer += c
        elif c == '(':
            stack.push(c)
        elif c == ')':
            while not stack.isEmpty() and stack.peek() != '(':
                answer += stack.pop()
            stack.pop()
        else:
            while not stack.isEmpty() and prec[c] <= prec[stack.peek()]:
                answer += stack.pop()
            stack.push(c)

    while not stack.isEmpty():
        answer += stack.pop()

    return answer