자료구조와 알고리즘 12강

자료구조와 알고리즘 12강

Posted by 동식이 블로그 on September 24, 2019

12강: 스택의 응용 - 수식의 후위 표기법

후위 표기법(Postfix Notation)이란?

  • 연산자를 두 피연산자의 뒤에 쓰는 방식
  • 일상에서 사용하는 수식의 표기법은 중위 표기법(Infix Notation)
  • 중위 표기법 (A + B) * (C + D) 를 후위 표기법으로 변환
1
A B + C D + *
  • A + B * C 를 변환한다면 ?
1
A B C * +
  • 위처럼 후위 표기법을 이용한 연산을 할 때 스택이 이용된다
연산과정

A * B + C 를 후위 표현식으로 연산하는 과정

  1. A는 피연산자이므로 적어준다

  2. *는 연산자이기 때문에 스택에 집어넣는다

  3. B는 피연산자이기 때문에 적는다

  4. +는 연산자이고, 스택이 비어있지 않으므로 스택에 있는것과의 우선순위를 비교

    4-1. 비교한 후 높은 연산자가 스택에 있기 때문에(*) 스택에서 꺼내고

    4-2. 낮은 연산자(+)는 비어있는 스택에 넣어준다

  5. C는 피연산자이기 때문에 적는다

  6. 수식이 끝났기 때문에 스택에 있는 연산자를 꺼내서 적어준다

  7. 결과 : A B * C +


A + B * C 를 후위 표현식으로 연산하는 과정

  1. A는 피연산자이므로 적어준다

  2. +는 연산자이기 때문에 스택에 넣어준다

  3. B는 피연산자이므로 적어준다

  4. *는 연산자이고, 스택이 비어있지 않으므로 스택에 있는것과의 우선순위를 비교

    4-1. 비교 후 높은 연산자(*)는 스택에 들어있지 않기 때문에 스택에 넣어준다

  5. C는 피연산자이기 때문에 적어준다

  6. 수식이 끝났기 때문에 스택에 있는 연산자를 꺼내서 적어준다

  7. 결과 : A B C * +


  • 스택의 우선순위 비교
    • 우선순위가 높은것을 스택에서 꺼내서 적어준다
    • 만약 동일하다면 먼저들어온, 즉 스택에 있는 연산자를 꺼내서 적어준다
    • 괄호가 있다면 괄호 우선순위를 가장 높게 !!
      • 여는 괄호는 스택에 push
      • 닫는 괄호를 만나면 여는 괄호가 나올 때 까지 pop 해주면 된다
      • 단, 연산자를 만났을 때 여는괄호 너머까지 pop하지 않도록 여는괄호의 우선순위는 가장 낮게 설정해 주어야 한다


괄호가 있는 수식 A * (B + C) 를 후위 표기식으로 연산하는 과정

  1. A는 피연산자 이므로 적어준다
  2. *는 연산자 이기 때문에 스택에 넣어준다
  3. ( (여는괄호)를 만났기 때문에 스택에 넣어준다
  4. +는 현재 스택에 (가 있기 때문에 그 위에 넣어준다
  5. C 는 피연산자 이므로 적어준다
  6. ) (닫는괄호)를 만났기 때문에 현재 스택에서 ((여는괄호)를 만나기 전까지 연산자들을 꺼내 적어준다
  7. 수식이 끝났기 때문에 스택에 남아있는 연산자를 꺼내준다
  8. 결과 : A B C + *


괄호가 두개 있는 수식 (A + B) * (C + D) 를 후위 표기식으로 연산하는 과정

  1. ( 를 스택에 넣어준다
  2. A 는 피연산자 이므로 적어준다.
  3. + 연산자는 현재 스택에 ( 가 있기 때문에 그 위에 넣어준다
  4. B 는 피연산자 이므로 적어준다.
  5. ) 를 만났기 때문에 스택에서 ( 를 만날 때까지 스택에서 꺼내 적어준다
  6. * 는 연산자이므로 스택에 넣어주는데, 스택이 비어있기 때문에 그대로 넣어준다
  7. ( 를 현재 스택의 위에 넣어준다
  8. C 는 피연산자 이므로 적어준다
  9. + 는 현재 스택에 ( 가 있기 때문에 그 위에 넣어준다
  10. D 는 피연산자 이므로 적어준다
  11. ) 를 만났기 때문에 스택에서 ( 를 만날 때까지 스택에서 꺼내서 적어준다
  12. 수식이 끝났기 때문에 스택에 남아있는 연산자를 꺼내준다
  13. 결과 : A B + C D + *
  • 다른 예제
    • (A + (B - C)) * D 는 ?
      • A B C - + D *
    • A * (B - (C + D)) 는?
      • A B C D + - *


알고리즘의 설계

  • 연산자의 우선순위 설정
1
2
3
4
5
prec = {
  '*':3, '/':3,
  '+':2, '-':2,
  '(':1
}
  • 중위 표현식을 왼쪽부터 한 글자씩 읽어서
    • 피연산자이면 그냥 출력
    • ( 이면 스택에 push
    • ) 이면 ( 이 나올 때까지 스택에서 pop, 출력
    • 연산자이면 스택에서 이보다 높(거나 같)은 우선순위 것들을 pop, 출력
    • 그리고 다 pop해서 출력한 후에는 지금 만난 연산은 스택에 push
  • 스택에 남아있는 연산자는 모두 pop, 출력


실습

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
'''
스택의 맨 위에 있는 연산자와의 우선순위 비교, 스택의 peek() 연산 이용
스택에 남아있는 연산자 모두 pop()하는 순환문 while not S.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,
}

import string

def solution(S):
    eng = string.ascii_lowercase
    myStack = ArrayStack()
    answer = ''
    for i in S:
        if(i in eng):
            answer += i
        else:
            if(i == "("):
                myStack.push(i)
            elif(i == ")"):
                item = None
                while(not myStack.isEmpty()):
                    item = myStack.pop()
                    if(item == "("):
                        break
                    else:
                        answer += item
            else:
                if(not myStack.isEmpty()):
                    item = myStack.peek()
                    if(prec[item] >= prec[i]):
                      # 여기서 한번더 처리를 해주는 이유는
                      # 아래의 예외사항들을 처리해 주기 위해서
                        while(not myStack.isEmpty()):
                            item = myStack.pop()
                            answer += item
                        myStack.push(i)
                    else:
                        myStack.push(i)
                else:
                    myStack.push(i)
                    
    while(not myStack.isEmpty()):
        item = myStack.pop()
        answer += item       
            
    return answer 
1
2
3
4
5
6
7
8
# 예외사항
입력값 > A+B*C-D/E
기댓값 > ABC*+DE/-
실행한 결과값 > 'ABC*DE/-+'

입력값 > A+B*C-D
기댓값 > ABC*+D-
실행한 결과값 > 'ABC*D-+


본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니다.

출처 : 프로그래머스 : 어서와! 자료구조와 알고리즘은 처음이지?