Evaluate Reverse Polish Notation - 리트코드

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

평가

결과 : 성공
풀이시간 : 7분

아이디어

숫자는 스택에 넣고, 연산자가 나오면 스택에서 두 개의 값을 꺼내 연산합니다. 그 후 연산결과를 스택에 저장합니다.

수도코드

Stack stack 선언;
for(num : nums):
  if 숫자면:
    스택에 넣기
  else:
    int b = 스택에서 꺼내기
    int a = 스택에서 꺼내기
    a (연산자) b 를 스택에 넣는다
return 스택.push();

정답 코드

스택은 Stack를 써도 되는데 시간복잡도를 조금이라도 줄이고 싶어서 int[]와 now로 커스텀해 사용했습니다.

• Stack의 push 가 일어나면 now 자리에 데이터를 넣습니다. 그리고 now를 오른쪽으로 한 칸 이동합니다.
• Stack의 pop 이 일어나면 now - 1 위치에 있는 데이터를 반환합니다. 그리고 now를 왼쪽으로 한 칸 이동합니다.
• Stack의 사이즈를 구해야 한다면 now를 반환하면 됩니다.

사실 코테 수준에서는 Stack을 써도 무방합니다. 저도 LeetCode에서 몇 등인지 체크해서 그렇지 실전에서는 Stack 사용합니다.

class Solution {
    public int evalRPN(String[] tokens) {
        int[] stack = new int[tokens.length];
        int now = 0;

		// 연산자면 스택에 들어있는 두 개를 꺼낸다
        // 가장 최근에 들어간거: b
        // 2번째로 최근에 들어간거: a
        // (a 연산자 b) 결과를 다시 스택에 저장한다.
        for(String token: tokens) {
            if (token.equals("+")) {
                now--;
                int b = stack[now];
                int a = stack[now - 1];
                stack[now] = a + b;
            } else if (token.equals("-")) {
                now--;
                int b = stack[now];
                int a = stack[now - 1];
                stack[now] = a - b;                
            } else if (token.equals("*")) {
                now--;
                int b = stack[now];
                int a = stack[now - 1];
                stack[now] = a * b;
            }else if (token.equals("/")) {
                now--;
                int b = stack[now];
                int a = stack[now - 1];
                stack[now] = a / b;
            } else {
            	// 만약 숫자가 나오면 스택에 그대로 넣어준다.
                stack[now++] = Integer.parseInt(token);
            }
        }

        return stack[0];
    }
}