백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-1935 후위 표기식2 편 (python)

문제 살펴보기!!

문제 링크 :https://www.acmicpc.net/problem/1935

솔루션 살펴보기!!

import sys

def input():
    return sys.stdin.readline().rstrip()

def postfix_evaluation(expression, values):
    operators = {
        '+': lambda b, a: a + b,
        '-': lambda b, a: a - b,
        '*': lambda b, a: a * b,
        '/': lambda b, a: a / b
    }
    
    stack = []
    value_mapping = {}
    
    # 문자와 값을 매핑
    value_iter = iter(values)
    for char in expression:
        if char.isalpha() and char not in value_mapping:
            value_mapping[char] = next(value_iter)
    
    # 후위 표기법 수식 계산
    for char in expression:
        if char in operators:  # 연산자일 경우
            b = stack.pop()
            a = stack.pop()
            stack.append(operators[char](b, a))
        else:  # 피연산자일 경우
            stack.append(value_mapping[char])
    
    # 결과 출력
    return stack[0]

# 입력 처리
N = int(input())
expression = input()
values = [int(input()) for _ in range(N)]

# 결과 계산 및 출력
result = postfix_evaluation(expression, values)
print(f"{result:.2f}")

반응형

코드의 상세 내용 및 흐름

이 코드는 후위 표기법(Postfix Notation)을 사용하여 주어진 수식을 계산하는 프로그램입니다. 후위 표기법은 연산자가 피연산자 뒤에 나오는 수식 형식으로, 이를 사용하면 괄호 없이도 수식을 명확하게 표현할 수 있습니다. 이를 통해 피연산자와 연산자 처리 순서를 고려한 계산을 수행합니다.

코드 흐름

1. 입력 처리:
   • N = int(input()): 사용자가 입력하는 변수를 받을 숫자의 개수를 입력받습니다.
   • expression = input(): 후위 표기법으로 표현된 수식을 입력받습니다. 여기에는 문자(피연산자)와 연산자들이 혼합되어 있습니다.
   • values = [int(input()) for _ in range(N)]: 각 문자에 대응하는 숫자 값을 입력받아 리스트에 저장합니다.
2. 후위 표기법 수식 계산:
   • postfix_evaluation(expression, values) 함수가 호출되어 계산을 수행합니다.
   • 이 함수에서는 다음과 같은 과정을 거칩니다.

연산자와 그에 해당하는 동작 정의

operators = {
    '+': lambda b, a: a + b,
    '-': lambda b, a: a - b,
    '*': lambda b, a: a * b,
    '/': lambda b, a: a / b
}

각 연산자에 대한 동작을 람다 함수로 미리 정의해 놓았습니다. 이렇게 함으로써 연산자에 대한 조건문을 간소화할 수 있습니다.

문자와 숫자 매핑

value_iter = iter(values)
for char in expression:
    if char.isalpha() and char not in value_mapping:
        value_mapping[char] = next(value_iter)

수식에 있는 문자를 피연산자로 인식하여, 입력받은 숫자 값들과 매핑합니다. next(value_iter)를 사용해 값을 하나씩 차례대로 할당합니다.

후위 표기법 처리

for char in expression:
    if char in operators:  # 연산자일 경우
        b = stack.pop()
        a = stack.pop()
        stack.append(operators[char](b, a))
    else:  # 피연산자일 경우
        stack.append(value_mapping[char])

수식을 순차적으로 탐색하면서, 연산자인 경우 스택에서 두 개의 피연산자를 꺼내 해당 연산을 수행한 결과를 다시 스택에 넣고, 피연산자인 경우에는 대응하는 숫자를 스택에 넣습니다.

결과 반환: 모든 연산이 끝나면 스택에 남은 최종 결과를 반환하고 출력합니다

return stack[0]

728x90

알아야 할 주요 개념

• 후위 표기법 (Postfix Notation)
  • 수식에서 연산자가 피연산자 뒤에 위치하는 표기법입니다. 예를 들어, 일반적인 중위 표기법에서는 a + b라고 하지만, 후위 표기법에서는 a b +가 됩니다.
  • 후위 표기법은 괄호를 사용하지 않아도 연산의 순서를 명확히 할 수 있는 장점이 있습니다.
  • 컴퓨터 계산에 적합한 방식이며, 스택을 이용해 쉽게 처리할 수 있습니다.
• 스택 (Stack)
  • 후입선출(LIFO, Last In First Out) 구조의 자료구조입니다.
  • 후위 표기법 계산에서 스택은 매우 중요한 역할을 합니다. 피연산자를 스택에 쌓아두고, 연산자가 나왔을 때 스택에서 두 개의 피연산자를 꺼내어 연산 후 다시 스택에 넣는 방식으로 계산을 수행합니다.
• 람다 함수 (Lambda Function)
  • 람다 함수는 한 줄로 정의되는 익명 함수입니다. 여기서는 연산자에 해당하는 동작을 짧게 정의하기 위해 사용되었습니다.

'+': lambda b, a: a + b

 

이 코드는 + 연산자가 나왔을 때 a + b를 계산하는 익명 함수를 정의한 것입니다.

• 딕셔너리 (Dictionary)
  • 딕셔너리는 키-값 쌍으로 데이터를 저장하는 자료구조입니다. 여기서는 문자와 해당하는 숫자를 매핑하기 위해 사용되었습니다.

value_mapping = {}
value_mapping[char] = next(value_iter