1. 문제 설명
- 주어진 문자열 배열
tokens은 역 폴란드 표기법 으로 된 산술 식을 나타냅니다.
- 식을 계산하세요. 식의 값을 나타내는 정수를 반환하세요.
- 참고 사항:
- 유효한 연산자는 '+', '-', '*', '/'입니다.
- 각 피연산자는 정수이거나 다른 식일 수 있습니다.
- 두 정수 사이의 나눗셈은 항상 0으로 절단됩니다.
- 0으로 나누는 경우는 없습니다.
- 입력은 역 폴란드 표기법으로 된 유효한 산술 식을 나타냅니다.
- 답변과 중간 계산은 32비트 정수로 나타낼 수 있습니다.
2. 접근 방법
Stack과 Switch문을 사용하여 문제를 해결하였습니다.
- 반복문으로 문자열
token을 순회하며 연산자를 찾을 때까지 피연산자를 stack에 저장합니다.
- 연산자를 찾으면
stack의 데이터를 .pop하여 가장 최근의 데이터를 가져와 찾은 연산자로 연산을 합니다. 연산한 결과는 다음 연산을 위해 다시 .push 하여 저장합니다.
- 이때 연산자
+, *는 피연산자 순서가 바뀌어도 결과에 차이를 주지 않지만, 연산자 -, /는 순서에 따라 결과값이 다르기 때문에 연산 시 주의해야 합니다.
3. 구현 코드
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(String c : tokens){
int a, b;
switch(c){
case "+" :
stack.push(stack.pop() + stack.pop()); break;
case "*" :
stack.push(stack.pop() * stack.pop()); break;
case "-" :
a = stack.pop(); b = stack.pop();
stack.push(b - a); break;
case "/" :
a = stack.pop(); b = stack.pop();
stack.push(b / a); break;
default : stack.push(Integer.parseInt(c)); break;
}
}
return stack.pop();
}
}
- 시간 복잡도 : O(n)
- 공간 복잡도 : O(n)
4. 최종 회고
- 이전에 stack을 풀어 본 경험이 있어 문제를 해결하는데 재미있었습니다. 이전에는 다소 가독성이 좋지 않았지만 이번에는 더 깔끔하게 코드를 만들어 만족합니다.
