Evaluate Reverse Polish Notation
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are
+
, -
, *
, /
. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
Solution: Use a stack.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | public class Solution { private boolean isNumber(String s) { if (s.charAt(0) == '-' && s.length() > 1) { return true; } if (s.charAt(0) >= '0' && s.charAt(0) <= '9') { return true; } return false; } private int evalOp(int first, int second, String s) { if (s.equals("+")) { return first + second; } if (s.equals("-")) { return first - second; } if (s.equals("*")) { return first * second; } if (s.equals("/")) { return first / second; } return 0; } public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<Integer>(); for (String s : tokens) { if (isNumber(s)) { stack.push(Integer.parseInt(s)); } else { int second = stack.pop(); int first = stack.pop(); int result = evalOp(first, second, s); stack.push(result); } } return stack.pop(); } } |
No comments:
Post a Comment