12강: 수식의 후위 표기법

유태형·2022년 3월 8일

알고리즘 파이썬 프로그래머스

알고리즘 - Python

목록 보기

8/16

12강 요약

연산자의 위치에 따라 중위연산자와 후위연산자에 대해 알아보고 중위연산자를 스택을 이용하여 후위연산자로 전환

후위 연산자란?

피연산자 연산자 피연산자 구조인 중위여산자와 달리 피연산자 피연산자 연산자 구조로 연산자가 가장 마지막에 위치함, 또 중위연산자와 달리 괄호를 사용하지 않아도 되는 장점이 존재함

A + B 는 AB+
(A + B) * (C + D)는 AB+CD+*로 전환할 수 있다.
A+B*C 는 ABC*+, A*B+C는 AB*C+로 전환할 수 있다.

중위 연산자를 후위 연산자로

1.피연산자는 바로 반영
2.여는 괄호와 닫는 괄호는 따로 처리
3.연산자는 우선순위에 맞게 처리

피연산자는 바로 반영

딱히 따로 처리하는 로직이 필요없다.

여는 괄호와 닫는 괄호는 따로 처리

여는 쪽과 닫는쪽의 처리방법이 다른데 여는 괄호(는 그냥 스택에 넣어주면 된다.닫는 괄호)가 나오면 여는 괄호가 나올때까지 스택에 있는 연산자들을 출력한다.

연산자는 우선순위에 맞게 처리

연산자가 나오면 스택에 있는 연산자와의 우선순위를 비교한다. 스택에 존재하는 연산자 우선순위랑 비교하며 지금 연산자가 더 우선순위가 높으면 스택에 저장하고 스택에 저장된 연산자가 우선순위가 더 높다면 우선순위가 높거나 같은 연산자들은 모두 출력한 다음 현재 연산자를 스택에 저장한다.

문제

중위표현 수식 --> 후위표현 수식

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 s in S:
        if s.isalpha(): #피연산자
            answer += s
        elif s == '(': #여는 괄호는 무조건 넣기
            opStack.push(s)
        elif s == ')': #닫는 괄호는
            while opStack.peek() != '(': #여는 괄호 나올때까지
                answer += opStack.pop() #pop
            opStack.pop()
        else: #연산자
            if opStack.isEmpty(): #비었으면 그냥 넣기
                opStack.push(s)
            else: #비어있지 않음, 우선순위 비교
                while opStack.isEmpty() == False and prec[opStack.peek()] >= prec[s]:
                    answer += opStack.pop()
                opStack.push(s)
                
        
    while not opStack.isEmpty():
        answer += opStack.pop()
        
    return answer