소개
스택은 컴퓨터 과학에서 흔히 쓰이는 컬렉션의 한 종류예요.
스택은 push와 pop이라는 두 가지 핵심 연산으로 정의돼요.
push는 스택 맨 위에 원소를 추가하고, pop은 맨 위의 원소를 제거해서 반환해요.
스택은 접시를 쌓아 놓은 것과 비슷하다고 생각해 봐요.
쌓인 접시 맨 위에 접시를 하나 더 올리거나, 맨 위에 있는 접시를 가져갈 수 있어요.
아래쪽에 있는 접시를 꺼내려면 그 위에 쌓인 접시를 모두 치워야 해요.
Rust의 벡터 구현인 std::vec::Vec은 push()와 pop() 메서드를 써서 스택처럼 활용할 수 있어요.
push()는 Vec의 끝에 원소를 추가하고, pop()은 마지막 원소를 제거해서 반환해요.
이 연산은 매우 빠를 수 있기 때문에(빅 오 표기법에서 O(1)), Vec을 사용하는 가장 관용적인 방법 중 하나예요.
스택은 여러 원소를 특정한 순서로 담아 두는 데 유용해요.
마지막에 넣은 원소가 가장 먼저 반환되기 때문에, 스택은 흔히 LIFO(Last-In, First-Out)라고 불려요.
이렇게 원래부터 정해져 있는 순서는 여러 가지 일에 활용할 수 있는데, 역폴란드 표기법을 계산할 때 상태를 추적하는 것도 그중 하나예요.
지침
1. 개요
역폴란드 표기법(RPN)은 수학적 표현을 작성하는 방법이에요.
전통적인 중위 표기법과 달리, RPN에서는 연산자가 피연산자 뒤에 와요.
예를 들어, 다음과 같이 쓰는 대신:
2 + 2
다음과 같이 써요:
2 2 +
역폴란드 표기법의 가장 큰 장점은 중위 표기법보다 파싱하기가 훨씬 간단하다는 점이에요.
RPN을 쓰면 복잡한 식에서 연산 순서나 괄호가 필요 없어요.
예를 들어:
(4 + 8) / (7 - 5)
는 다음과 같이 쓸 수 있어요.
4 8 + 7 5 - /
두 경우 모두 식의 계산 결과는 6이에요.
2. 예시
그 복잡한 식을 직접 계산해 봐요.
도입부에서 배웠듯이, RPN을 계산하려면 스택이 필요해요.
이 스택은 연산자가 연산할 숫자 값을 담아 두는 데 사용돼요.
계산기를 빈 스택으로 시작한 다음, 각 요소를 하나씩 계산해요.
먼저 4를 만나므로, 방금 만든 스택에 이 값을 넣어요.
4
다음으로 8을 만나요.
이것도 스택에 넣어요.
4 8
이제 +를 만나요.
맨 위에 있는 두 값(4와 8)을 꺼내서
더한 다음,
그 합을 다시 스택에 넣어요.
12
7, 5, -에 대해서도 비슷한 과정을 거쳐요.
12 7
12 7 5
12 2
이제 /를 만나요.
마지막으로 만난 게 -였지만,
스택에는 두 개의 요소가 있어요.
두 요소를 꺼내서
나눈 다음,
그 결과를 다시 스택에 넣어요.
6
마지막으로, 스택에 요소가 정확히 하나만 남아 있으므로, 이 식의 계산 결과는 6이라고 할 수 있어요.
3. 목표
목표는 역폴란드 표기법 순서로 주어진 입력 목록을 계산하고, 스택에 남은 마지막 요소를 반환하는 계산기를 작성하는 거예요.
끝났을 때 스택에 요소가 정확히 하나 남아 있지 않으면 None을 반환해요.
피연산자가 너무 적은 연산자가 있으면(예를 들어 입력이 2 +라면), None을 반환해요.
시작점으로 다음 열거형과 뼈대만 잡힌 함수가 주어져요.
#[derive(Debug)]
pub enum CalculatorInput {
Add,
Subtract,
Multiply,
Divide,
Value(i32),
}
pub fn evaluate(inputs: &[CalculatorInput]) -> Option<i32> {
todo!(
"Given the inputs: {inputs:?}, evaluate them as though they were a Reverse Polish notation expression"
);
}
학습 연습 문제
