← 전체 회차
A-023● Day 232026.05.27mediumleetcode #150neetcode150

역폴란드 표기법 계산

#array#math#stack
↗ leetcode #150 · evaluate-reverse-polish-notation
01

문제

· problem
P.023

역폴란드 표기법 계산

↗ leetcode #150

산술 표현식을 역폴란드 표기법(RPN)으로 나타낸 문자열 배열 tokens가 주어집니다. 표현식을 계산하여 결과를 나타내는 정수를 반환하세요. 주의: - 유효한 연산자는 '+', '-', '*', '/'입니다. - 각 피연산자는 정수입니다. - 두 정수의 나눗셈은 항상 0을 향해 절단됩니다. - 0으로 나누는 경우는 없습니다. - 입력은 유효한 역폴란드 표기법 산술식입니다. - 답과 모든 중간 계산 결과는 32비트 정수로 표현 가능합니다.

제약
  • · 1 ≤ tokens.length ≤ 10⁴
  • · tokens[i] is either an operator (+, -, *, /) or an integer in range [-200, 200]
  • · Division truncates toward zero
  • · No division by zero
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
["2","1","+","3","*"]
9
example 2input → output
["4","13","5","/","+"]
6
example 3input → output
["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
22
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    "0을 향해 절단한다"는 것이 나눗셈에서 무엇을 의미하나요?
  • ☐
    뺄셈과 나눗셈에서 피연산자의 순서가 중요한 이유는 무엇인가요?
  • ☐
    왜 스택 데이터 구조가 역폴란드 표기법 평가에 적합한가요?
  • ☐
    "-11"처럼 음수 피연산자를 어떻게 구분하나요?
  • ☐
    덧셈과 곱셈은 교환법칙이 성립하는데 뺄셈과 나눗셈은 아닌 점을 어떻게 처리하나요?
  • ☐
    왜 float(b) / a를 사용한 다음 int()로 변환하나요?
  • ☐
    재귀를 사용하여 역폴란드 표기법을 평가할 수 있을까요?
  • ☐
    모든 중간 계산 결과를 모두 저장해야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 스택 초기화
○
stack = []
○
queue = []
○
nums = {}
○
stack = None
step 2· 토큰 순회
○
for c in tokens:
○
for i in range(len(tokens)):
○
for c in reversed(tokens):
step 3· 덧셈 연산 (교환법칙 성립)│ │ 중첩
○
stack.append(stack.pop() + stack.pop())
○
a, b = stack.pop(), stack.pop(); stack.append(a + b)
○
stack.append(stack[0] + stack[1])
step 4· 뺄셈 연산 (순서 보존)│ │ 중첩
○
stack.append(b - a)
○
stack.append(a - b)
○
stack.append(stack.pop() - stack.pop())
step 5· 나눗셈 (0을 향해 절단)│ │ 중첩
○
stack.append(int(float(b) / a))
○
stack.append(b // a)
○
stack.append(int(b / a))
step 6· 피연산자 파싱│ │ 중첩
○
stack.append(int(c))
○
if c.isdigit(): stack.append(int(c))
○
stack.append(float(c))
step 7· 결과 반환
○
return stack[0]
○
return sum(stack)
○
return stack.pop()
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def evalRPN(self, tokens: List[str]) -> int:
3
        stack = []
4
        for c in tokens:
5
            if c == "+":
6
                stack.append(stack.pop() + stack.pop())
7
            elif c == "-":
8
                a, b = stack.pop(), stack.pop()
9
                stack.append(b - a)
10
            elif c == "*":
11
                stack.append(stack.pop() * stack.pop())
12
            elif c == "/":
13
                a, b = stack.pop(), stack.pop()
14
                stack.append(int(float(b) / a))
15
            else:
16
                stack.append(int(c))
17
        return stack[0]
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
["2","1","+","3","*"]
→
9
case 2
["4","13","5","/","+"]
→
6
case 3
["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
→
22
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.