-
leetcode top interview 150 | Evaluate Reverse Polish Notation | StackPS 2023. 8. 31. 17:19
Question
후위표기법으로 나타낸 산술표현식이 문자열 배열로 주어졌을때 산출되는 답을 반환
Accepted Code - Stack
import java.util.*; import java.util.regex.Pattern; class Solution { public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for(String token : tokens){ if(Pattern.matches("[+\\-*/]", token)){ int a = stack.pop(); int b = stack.pop(); switch(token){ case "+" -> stack.push(a+b); case "-" -> stack.push(b-a); case "*" -> stack.push(a*b); case "/" -> stack.push(b/a); } }else{ stack.push(Integer.parseInt(token)); } } return stack.pop(); } }
Solve
피연산자는 저장했다가 연산자를 만날 경우 저장했던 피연산자를 꺼내 처리하는 방식이 떠올랐다.
따라서 LIFO(Last In, First Out) 구조인 stack을 활용하여 피연산자는 push 해주고, 연산자일 경우엔 피연산자 두개를 pop하여 연산한 결과를 다시 push하도록 했다. 순회가 끝나면 stack에 마지막 연산 결과가 저장되어있으므로 pop으로 결과를 반환한다.
연산자/숫자 확인으로 정규표현식을 활용했는데, regex.Pattern에 있는 matches를 사용했다. 정규표현식에서 빼기 기호는 범위를 나타내기때문에 구분하기 위해 \\를 앞에 붙여줬다.
Evaluate Reverse Polish Notation - LeetCode
Can you solve this real interview question? Evaluate Reverse Polish Notation - You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation [http://en.wikipedia.org/wiki/Reverse_Polish_notation]. Evaluate t
leetcode.com
'PS' 카테고리의 다른 글