[알고리즘 강의] 파트12. 스택의 응용: 수식의 후위 표기법

중위 표기법과 후위 표기법

중위 표기법 (infix notation)

- 연산자가 피연산자들의 사이에 위치

-  우리가 익숙한 표기법

 

 

 

후위 표기법 (postfix notation) 

- 연산자가 피연산자들의 뒤에 위치

 

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

- 피연산자는 그냥 출력

- 첫 연산자는 스택에 푸시

- 다음 연산자의 경우 스택에 들어있던 연산자의 우선순위가 같거나 높으면 스택에 들어있던 연산자를 pop한 후에 스택에 푸시, 우선순위가 낮을 경우 그냥 스택에 푸시

- 수식이 끝나는 지점에서 스택에 남아있는 연산자들을 모두 pop

 

괄호의 처리

[중위] (A + B) * C

[후위] A B + C *

 

여는 괄호는 스택에 push

닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop

 

[중위] A * (B + C)

[후위] A B C + *

 

연산자를 만났을 때, 여는 괄호 너머까지 pop하지 않도록

여는 괄호의 우선순위는 가장 낮게 설정

 

예제

[중위] (A + B) * (C + D)

[후위] A B + C D + *

 

[중위] (A + (B - C)) * D

[후위] A B C - + D *

 

[중위] A * (B - (C + D))

[후위] A B C D + - *

 

 

실습 과제 - 중위표현 수식 --> 후위표현 수식

알고리즘의 설계

연산자의 우선순위 설정

prec = {

          ' * ': 3, ' / ': 3,

          ' + ': 2, ' - ': 2,

          ' ( ': 1

}

 

중위 표현식을 왼쪽부터 한 글자씩 읽어서

    피연산자이면 그냥 출력

    '(' 이면 스택에 push

    ')' 이면 '(' 이 나올 때까지 스택에서 pop, 출력

    연산자이면 스택에서 이보다 높(거나 같)은 우선순위 것들을 pop, 출력

        그리고 이 연산자는 스택에 push

스택에 남아 있는 연산자는 모두 pop, 출력

 

코드의 구현 - 힌트

스택의 맨 위에 있는 연산자와의 우선순위 비교

-> 스택의 peek() 연산 이용

스택에 남아 있는 연산자 모두 pop() 하는 순환문

-> while not opStack.isEmpty():

 

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 c in S:
        if c.isalpha():
            answer += c
        elif c=='(':
            opStack.push(c)
        elif c==')':
            while not opStack.isEmpty():
                pop_s = opStack.pop()
                if pop_s=='(':
                    break
                answer+=pop_s
            
        elif c in '*/+-':
            while not opStack.isEmpty():
                if prec[opStack.peek()] >= prec[c]:
                    answer+=opStack.pop()
                else:
                    break
            opStack.push(c)
                
    while not opStack.isEmpty():
        answer+=opStack.pop()
    
    return answer

 

* 프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?' 강의를 듣고 정리하였습니다.