후위 표기법 2

소괄호를 포함한 후위 표기법 바꾸기

소괄호()는 *보다 우선순위가 높다.

후위 표기법은 우선순위가 높은 것을 먼저 출력하므로, 열린 소괄호가 나오면 스택에 넣는다.

이후 닫힌 소괄호가 나오면 스택에 열린 소괄호 나올 때 까지 pop하여 연산자를 결과값에 추가한다.

  • 괄호는 변수에 추가하면 안되므로 스택에서 pop하여 제거한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def solution(str):
    priority = {'+':2,'-':2,'*':1,'/':1}
    result = ''
    s = []

    for x in str:
        if x.isnumeric():
            result += x
        elif x == '(':
            s.append(x)
        elif x == ')':
            while s[-1] != "(":
                result += s.pop()
            s.pop()
        elif x in priority:
            if s and s[-1] != '(' and priority[s[-1]] < priority[x]:
                result += s.pop()
            s.append(x)

    while s:
        result += s.pop()

    return result
  • 코딩테스트를 본다고 생각하고 리스트를 활용하여 위 문제를 풀어보았다.
  • isnumeric() 함수는 문자열이 숫자인지 판단하는 메서드이다.
  • stack의 top을 의미하는 s[-1] 슬라이싱을 활용하였다.
  • 빈 리스트는 논리값이 False라는 점을 활용하여 while 반복문을 실행했다.

후위 표기법 계산하기

  1. 문자열을 순회하면서 해당 문자가 숫자면 정수형으로 변환하여 스택에 push
  2. 연산자이면 스택에서 두 수를 pop하여 계산
  3. 스택은 후입선출이므로, 처음 pop한 수를 n2, 두번째 pop한 수를 n1으로 두고 (n1 연산자 n2)로 계산한다.
  4. 계산결과를 스택에 push
  5. 스택에 마지막에 저장된 값이 결과값이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def eval_postfix(expression):
    s = []
    for exp in expression:
        if exp.isnumeric():
            s.append(int(exp))
        elif exp != " ":
            n2 = s.pop()
            n1 = s.pop()
            if exp == '+':
                res = n1 + n2
            elif exp == '-':
                res = n1 - n2
            elif exp == '*':
                res = n1 * n2
            else:
                res = n1 / n2
            s.append(res)
    return s[0]