문제 설명

Reverse Polish Notation에서 산술 표현식의 값을 평가합니다.

유효한 연산자는 +, -, * 및/입니다. 각 피연산자는 정수 또는 다른 표현식일 수 있습니다.

두 정수 사이의 나눗셈은 0을 향해 잘려야 합니다.

주어진 RPN 표현식이 항상 유효함을 보장합니다. 즉, 표현식은 항상 결과로 평가되며 0으로 나누기 작업이 없습니다.

Reverse Polish notation (RPN), also known as Polish postfix notation or simply postfix notation, is a mathematical notation in which operators follow their operands, in contrast to Polish notation (PN), in which operators precede their operands.

샘플 테스트 케이스

예 1:

입력: 토큰 = ["2","1","+","3","*"]
출력: 9
설명: ((2 + 1) * 3) = 9
예 2:

입력: 토큰 = ["4","13","5","/","+"]
출력: 6
설명: (4 + (13/5)) = 6
예 3:

입력: 토큰 = ["10","6","9","3","+","-11","","/","","17","+","5 ","+"]
출력: 22
설명: ((10 * (6/((9 + 3) * -11))) + 17) + 5
= ((10 * (6/(12 * -11))) + 17) + 5
= ((10 * (6/-132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

제약

1 <= 토큰.길이 <= 104

tokens[i]는 "+", "-", "*"또는 "/"연산자이거나 [-200, 200] 범위의 정수입니다.

접근하다 :

접근 방식은 스택을 사용하여 매우 간단합니다.

여기에서 숫자를 볼 때마다 스택에 넣기만 하면 됩니다.

+ 연산자가 표시되면 상위 2개 요소를 팝 아웃하고 추가한 다음 다시 스택에 넣습니다.

* 연산자가 표시되면 상위 2개 요소를 꺼내서 곱하고 다시 스택에 넣습니다.

- 연산자를 볼 때 상위 2개 요소를 팝아웃해야 하지만 b = stack.pop() - the first element we pop 및 a = stack.pop() - the second element we pop를 가정하고 이제 a/b를 나누어 스택에 다시 푸시합니다.

/ 연산자를 볼 때 상위 2개 요소를 팝아웃해야 하지만 b = stack.pop() - the first element we pop 및 a = stack.pop() - the second element we pop를 가정하고 이제 a-b를 빼서 스택으로 다시 푸시합니다.

암호

class Solution {
    public int evalRPN(String[] tokens) {
        if (tokens.length == 0 || tokens == null)
            return -1;
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (token.equals("+")) {
                stack.push(stack.pop() + stack.pop());
            }
            else if (token.equals("*")) {
                stack.push(stack.pop() * stack.pop());
            }
            else if (token.equals("-")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a - b);
            }
            else if (token.equals("/")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a / b);
            }
            else {
                stack.push(Integer.valueOf(token));
            }
        }
        return stack.pop();
    }
}

시간 복잡도와 공간 복잡도:

O(lengthOfInputArray) 시간 및 O(lengthOfInputArray) 공간.

테스트 사례를 사용한 코드 연습

입력 = ["10","6","9","3","+","-11","","/","","17","+","5", "+"]
답 = 22

Github 리포지토리:

Rohithv07 / LeetCodeTop인터뷰질문

Leetcode에서 논의된 Leetcode 상위 인터뷰 질문. https://leetcode.com/explore/interview/card/top-interview-questions

LeetCodeTop인터뷰질문

Leetcode에서 논의된 Leetcode 상위 인터뷰 질문. https://leetcode.com/explore/interview/card/top-interview-questions-easy/
또한 CodeSignal.com에서 답변한 질문: https://app.codesignal.com/



View on GitHub

Rohithv07 / LeetCode

해결된 LeetCode 문제.

LeetCode

해결된 LeetCode 문제.



View on GitHub