|
5 | 5 | importjava.util.Stack; |
6 | 6 |
|
7 | 7 | /** |
8 | | - * Evaluate the value of an arithmetic expression in Reverse Polish Notation. |
9 | | -
|
10 | | - Valid operators are +, -, *, /. Each operand may be an integer or another expression. |
11 | | -
|
12 | | - Some examples: |
13 | | -
|
14 | | - ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 |
15 | | - ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6 |
16 | | -
|
| 8 | + * 150. Evaluate Reverse Polish Notation |
| 9 | + * |
| 10 | + * Evaluate the value of an arithmetic expression in Reverse Polish Notation. |
| 11 | + * |
| 12 | + * Valid operators are +, -, *, /. Each operand may be an integer or another expression. |
| 13 | + * |
| 14 | + * Note: |
| 15 | + * |
| 16 | + * Division between two integers should truncate toward zero. |
| 17 | + * The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation. |
| 18 | + * |
| 19 | + * Example 1: |
| 20 | + * |
| 21 | + * Input: ["2", "1", "+", "3", "*"] |
| 22 | + * Output: 9 |
| 23 | + * Explanation: ((2 + 1) * 3) = 9 |
| 24 | + * |
| 25 | + * Example 2: |
| 26 | + * |
| 27 | + * Input: ["4", "13", "5", "/", "+"] |
| 28 | + * Output: 6 |
| 29 | + * Explanation: (4 + (13 / 5)) = 6 |
| 30 | + * |
| 31 | + * Example 3: |
| 32 | + * |
| 33 | + * Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] |
| 34 | + * Output: 22 |
| 35 | + * Explanation: |
| 36 | + * ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 |
| 37 | + * = ((10 * (6 / (12 * -11))) + 17) + 5 |
| 38 | + * = ((10 * (6 / -132)) + 17) + 5 |
| 39 | + * = ((10 * 0) + 17) + 5 |
| 40 | + * = (0 + 17) + 5 |
| 41 | + * = 17 + 5 |
| 42 | + * = 22 |
17 | 43 | */ |
18 | 44 | publicclass_150 { |
19 | 45 |
|
20 | | -publicintevalRPN(String[]tokens) { |
21 | | -Stack<String>stack =newStack<String>(); |
22 | | -Set<String>op =newHashSet(); |
23 | | -op.add("+"); |
24 | | -op.add("-"); |
25 | | -op.add("*"); |
26 | | -op.add("/"); |
| 46 | +publicstaticclassSolution1 { |
| 47 | +publicintevalRPN(String[]tokens) { |
| 48 | +Stack<String>stack =newStack<>(); |
| 49 | +Set<String>op =newHashSet(); |
| 50 | +op.add("+"); |
| 51 | +op.add("-"); |
| 52 | +op.add("*"); |
| 53 | +op.add("/"); |
27 | 54 |
|
28 | | -intexp =0; |
29 | | -Stringoperand1 =""; |
30 | | -Stringoperand2 =""; |
31 | | -for (inti =0;i <tokens.length;) { |
32 | | -while ((i <tokens.length) && (!op.contains(tokens[i]))) { |
33 | | -stack.push(tokens[i]); |
34 | | -i++; |
35 | | - } |
36 | | -if (i ==tokens.length) { |
37 | | -if (!stack.isEmpty()) { |
38 | | -returnInteger.parseInt(stack.pop()); |
39 | | - } |
40 | | - }elseif (op.contains(tokens[i])) { |
41 | | -if (!stack.isEmpty()) { |
42 | | -operand2 =stack.pop(); |
| 55 | +intexp =0; |
| 56 | +Stringoperand1 =""; |
| 57 | +Stringoperand2 =""; |
| 58 | +for (inti =0;i <tokens.length; ) { |
| 59 | +while ((i <tokens.length) && (!op.contains(tokens[i]))) { |
| 60 | +stack.push(tokens[i]); |
| 61 | +i++; |
43 | 62 | } |
44 | | -if (!stack.isEmpty() && !op.contains(stack.peek())) { |
45 | | -operand1 =stack.pop(); |
| 63 | +if (i ==tokens.length) { |
| 64 | +if (!stack.isEmpty()) { |
| 65 | +returnInteger.parseInt(stack.pop()); |
| 66 | + } |
| 67 | + }elseif (op.contains(tokens[i])) { |
| 68 | +if (!stack.isEmpty()) { |
| 69 | +operand2 =stack.pop(); |
| 70 | + } |
| 71 | +if (!stack.isEmpty() && !op.contains(stack.peek())) { |
| 72 | +operand1 =stack.pop(); |
| 73 | + } |
| 74 | +if (tokens[i].equals("+")) { |
| 75 | +exp =Integer.parseInt(operand1) +Integer.parseInt(operand2); |
| 76 | + }elseif (tokens[i].equals("-")) { |
| 77 | +exp =Integer.parseInt(operand1) -Integer.parseInt(operand2); |
| 78 | + }elseif (tokens[i].equals("*")) { |
| 79 | +exp =Integer.parseInt(operand1) *Integer.parseInt(operand2); |
| 80 | + }elseif (tokens[i].equals("/")) { |
| 81 | +exp =Integer.parseInt(operand1) /Integer.parseInt(operand2); |
| 82 | + }else { |
| 83 | +exp =Integer.parseInt(operand2); |
| 84 | + } |
| 85 | +stack.push(String.valueOf(exp)); |
| 86 | +i++; |
46 | 87 | } |
47 | | -if (tokens[i].equals("+")) { |
48 | | -exp =Integer.parseInt(operand1) +Integer.parseInt(operand2); |
49 | | - }elseif (tokens[i].equals("-")) { |
50 | | -exp =Integer.parseInt(operand1) -Integer.parseInt(operand2); |
51 | | - }elseif (tokens[i].equals("*")) { |
52 | | -exp =Integer.parseInt(operand1) *Integer.parseInt(operand2); |
53 | | - }elseif (tokens[i].equals("/")) { |
54 | | -exp =Integer.parseInt(operand1) /Integer.parseInt(operand2); |
55 | | - }else { |
56 | | -exp =Integer.parseInt(operand2); |
57 | | - } |
58 | | -stack.push(String.valueOf(exp)); |
59 | | -i++; |
60 | 88 | } |
| 89 | +returnInteger.parseInt(stack.pop()); |
61 | 90 | } |
62 | | -returnInteger.parseInt(stack.pop()); |
63 | 91 | } |
64 | | - |
65 | 92 | } |