[LeetCode] 150. Evaluate Reverse Polish Notation

https://leetcode.com/problems/evaluate-reverse-polish-notation/

개요

1. 후위 표기법으로 표현된 배열을 계산하라

문제 해결 아이디어

• [4, 13, 5, /, +]
  • 1) 3번 인덱스 '/'와 2번 인덱스, 1번 인덱스가 연산에 참여한다.
  • 2) 그 결과인 3과 0번 인덱스가 연산에 참여한다.
    

• 연산자 기준으로 연산이 이뤄진다.
  - 연산자와 앞 두개의 숫자가 연산에 참여한다.
  • 그 결과와 직전 숫자가 다음 연산자와 연산을 이룬다.

🤨 Stack 을 이용해 숫자를 저장하자

의사 코드

1. 배열을 순차적으로 검사한다.
2. 주어진 문자가 숫자이다. (조건)
   2-1. 스택에 숫자를 push 한다.
3. 주어진 문자가 연산자이다. (조건)
   3-1. 스택에서 숫자를 두 개 pop한다.
   3-2. 숫자를 연산한다.
   3-3. 스택에 연산 결과를 push한다.
4. 최종 연산 결과를 pop 한다.

for(int i=0, 배열 끝까지){
	if(배열[i]가 숫자){
    	stack.push(배열[i])
    }else if(배열[i]가 +-*/){
    	결과 = stack.pop() +-*/ stack.pop()
        stack.push(결과)
    }
}
stack.pop()

결과

전체 코드 github 링크

다른 풀이

public int evalRPN(String[] tokens) {
        Stack<Integer> st2 = new Stack<>();

        for(String s : tokens){
            if(s.equals("+") || s.equals("*") || s.equals("/") || s.equals("-")){
                int b = st2.pop();
                int a = st2.pop();
                int res = cal(a, b, s.charAt(0));
                st2.push(res);
                
            } else {
                st2.push(Integer.parseInt(s));
            }
        }
        return st2.pop();
    }
    private int cal(int a, int b, char oprtr){
        if(oprtr == '+'){
            return a + b;
        } else if(oprtr == '-'){
            return a - b;
        } else if(oprtr == '*'){
            return a * b;
        } else {
            return a / b;
        }
    }

연산하는 부분을 따로 메서드로 추출해서 한 눈에 이해할 수 있었다.
나도 코드를 짤 때 이런 부분을 꼭 고려해야 해서 가독성을 높여야 할 것 같다.
이번에도 Stack이라는 자료구조가 java 기본 lang에 있는지 몰랐어서 한 번 사용해보고 싶다.