스택으로 구현하는 후위 표기법(RPN) 계산기란?
자바스크립트의 스택(Stack) 자료구조를 활용해 RPN(Reverse Polish Notation, 후위 표기법) 방식으로 입력된 수식을 계산하는 계산기를 만들어 보겠습니다.
후위 표기법은 연산자가 피연산자 뒤에 오는 표기 방식입니다. 괄호 없이도 연산 순서가 명확하게 결정되기 때문에 컴파일러나 전자계산기의 내부 로직 등 다양한 분야에서 활용되며, 스택을 함께 사용하면 수식을 단 한 번의 순회만으로 평가할 수 있다는 장점이 있습니다.
입력 데이터
다음과 같이 숫자(피연산자)와 연산자가 섞여 있는 배열이 입력으로 주어진다고 가정합니다.
const arr = [1, 5, '+', 6, 3, '-', '/', 7, '*'];처리 과정
배열의 요소를 왼쪽에서 오른쪽으로 하나씩 읽으면서 아래 규칙을 적용합니다.
- 피연산자(숫자)라면 스택에 push한다.
- 연산자라면 스택에서 두 개의 값을 pop해 연산한 뒤, 그 결과를 다시 스택에 push한다.
이 규칙대로 배열을 처리하면 다음과 같이 진행됩니다.
- 1 → 피연산자이므로 push → 스택: [1]
- 5 → 피연산자이므로 push → 스택: [1, 5]
- '+' → 1과 5를 pop해 더한 뒤 결과 6을 push → 스택: [6]
- 6 → 피연산자이므로 push → 스택: [6, 6]
- 3 → 피연산자이므로 push → 스택: [6, 6, 3]
- '-' → 6과 3을 pop해 뺀 뒤 결과 3을 push → 스택: [6, 3]
- '/' → 6과 3을 pop해 나눈 뒤 결과 2를 push → 스택: [2]
- 7 → 피연산자이므로 push → 스택: [2, 7]
- '*' → 2와 7을 pop해 곱한 뒤 결과 14를 push → 스택: [14]
모든 요소의 처리가 끝나면 스택에는 최종 결과만 남습니다.
const output = 14;구현 코드
const arr = [1, 5, '+', 6, 3, '-', '/', 7, '*'];
const stackCalculator = (arr = []) => {
const options = {
'+': (a, b) => a + b,
'-': (a, b) => a - b,
'*': (a, b) => a * b,
'/': (a, b) => a / b,
};
const stack = [];
arr.forEach(value => {
stack.push(
value in options
? options[value](...stack.splice(-2))
: value
);
});
return stack;
};
console.log(stackCalculator(arr));코드 동작 원리
- options 객체: 연산자 기호('+', '-', '*', '/')를 키로, 실제 연산을 수행하는 화살표 함수를 값으로 매핑합니다. 새로운 연산자를 추가할 때 이 객체에 항목만 추가하면 되므로 확장성이 뛰어납니다.
- stack 배열: push()와 splice()를 조합해 스택처럼 동작합니다.
- in 연산자: 현재 값이 options 객체에 존재하는지 확인해 해당 값이 연산자인지 피연산자인지 판별합니다.
- splice(-2): 스택 맨 위의 두 요소를 제거하면서 배열로 반환합니다. 전개 연산자(...)와 함께 사용해 두 값을 연산 함수의 인자 a, b로 전달합니다.
순회가 끝난 시점에 스택에 남아 있는 마지막 값이 곧 수식의 최종 계산 결과입니다.
실행 결과
[14]마무리 및 참고 사항
이 구현은 RPN 수식 평가의 핵심 로직을 보여주는 최소한의 예제입니다. 실제 서비스에 적용한다면 다음과 같은 예외 상황 처리를 추가하는 것이 좋습니다.
- 연산자를 만났는데 스택에 피연산자가 두 개 미만으로 남아 있는 경우 (잘못된 수식)
- 0으로 나누는 경우
- 숫자나 연산자 외의 알 수 없는 토큰이 포함된 경우
스택 기반의 후위 표기법 평가는 중위 표기법 수식을 후위 표기법으로 변환하는 알고리즘과 함께 학습하면 자료구조와 알고리즘에 대한 이해를 한층 깊게 할 수 있습니다.