백준1935 - 후위 표기식 2 (스택) Python

https://www.acmicpc.net/problem/1935

해당 문제는 피연산자 갯수 | 후위표기식 | 피연산자와 대응하는 값을 주고, 해당 식을 계산하는 문제다.

 

 

후위 표기식에 대한 설명

# 해당 문제에는 후위 표기식에 대한 설명이 없으므로 아래 설명으로 대체한다.

후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 
우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 
왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 
또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 
우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 
그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.
예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 
그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 
마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

# https://www.acmicpc.net/problem/1918

 

따라서, 후위 표기식은 우선 순위에 따라 이미 정렬된 문자열을 다루는 것이기 때문에

abc*+ 의 경우, b * c 를 먼저 처리한 뒤 a + (b * c)를 하여 값을 연산한다고 볼 수 있다.

 

그리고 이는 스택으로 풀이가 가능한데, 빈 스택에 연산자가 들어오기 전까지 스택에 알파벳을 추가하다가,

연산자가 들어올 경우 스택 마지막에 위치한 두 알파벳을 꺼내 연산한 뒤 다시 스택에 넣어주는 과정을 반복하는 것이다.

 

 

문제 해결 방식

 

먼저 문제 입력에서 등장한 후위 표기식에 등장하는 알파벳과, 이후 입력으로 주어진 숫자들을 대응시켜 저장해둔다.

이때, 해당 값이 알파벳인지 검증하고 이미 저장한 값이 아닌지 확인한 뒤 저장하는 과정이 필요하다.

 

def solution (data) :
  data.pop(0)
  arr = list(data.pop(0)) # 후위 표기식
  dic = {} # 대응하는 값을 저장하기 위한 딕셔너리
  i = 0
  for v in arr :
    # 알파벳 검증 | 중복 유무 검증
    if v.isalpha() and not dic.get(v, None) :
      dic[v] = int(data[i])
      i += 1

 

이후 위에서 설명한 스택(stack)을 활용하여 풀이한다.

 

아래는 파싱 과정없는 다른 후위 표기식 문제 풀이를 다룬 포스팅이므로 필요하다면 참고

2023.11.11 - [개발/algorithm] - 백준15815 - 천재 수학자 성필 (스택) Python

 

  stack = []
  
  table = {
    ('+') : lambda x,y : x + y,
    ('-') : lambda x,y : x - y,
    ('*') : lambda x,y : x * y,
    ('/') : lambda x,y : x / y
  }

  for v in arr :
    if v.isalpha() :
      stack.append(dic[v])
    else :
      a,b = stack.pop(),stack.pop()
      stack.append(table[v](b,a))

  result = stack[0]
  print('{:.2f}'.format(result))

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

def solution (data) :
  data.pop(0)
  arr = list(data.pop(0))
  dic = {}
  i = 0
  for v in arr :
    if v.isalpha() and not dic.get(v, None) :
      dic[v] = int(data[i])
      i += 1

  stack = []

  table = {
    ('+') : lambda x,y : x + y,
    ('-') : lambda x,y : x - y,
    ('*') : lambda x,y : x * y,
    ('/') : lambda x,y : x / y
  }

  for v in arr :
    if v.isalpha() :
      stack.append(dic[v])
    else :
      a,b = stack.pop(),stack.pop()
      stack.append(table[v](b,a))

  result = stack[0]
  print('{:.2f}'.format(result))

solution(input_data)