|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
| 3 | +importjava.util.Arrays; |
3 | 4 | importjava.util.HashSet; |
4 | 5 | importjava.util.Set; |
5 | 6 | importjava.util.Stack; |
6 | 7 |
|
7 | | -/** |
8 | | - * 150. Evaluate Reverse Polish Notation |
9 | | - * |
10 | | - * Evaluate the value of an arithmetic expression in Reverse Polish Notation. |
11 | | - * Valid operators are +, -, *, /. Each operand may be an integer or another expression. |
12 | | - * |
13 | | - * Note: |
14 | | - * Division between two integers should truncate toward zero. |
15 | | - * 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. |
16 | | - * |
17 | | - * Example 1: |
18 | | - * Input: ["2", "1", "+", "3", "*"] |
19 | | - * Output: 9 |
20 | | - * Explanation: ((2 + 1) * 3) = 9 |
21 | | - * |
22 | | - * Example 2: |
23 | | - * Input: ["4", "13", "5", "/", "+"] |
24 | | - * Output: 6 |
25 | | - * Explanation: (4 + (13 / 5)) = 6 |
26 | | - * |
27 | | - * Example 3: |
28 | | - * Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] |
29 | | - * Output: 22 |
30 | | - * Explanation: |
31 | | - * ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 |
32 | | - * = ((10 * (6 / (12 * -11))) + 17) + 5 |
33 | | - * = ((10 * (6 / -132)) + 17) + 5 |
34 | | - * = ((10 * 0) + 17) + 5 |
35 | | - * = (0 + 17) + 5 |
36 | | - * = 17 + 5 |
37 | | - * = 22 |
38 | | - */ |
39 | 8 | publicclass_150 { |
40 | 9 |
|
41 | 10 | publicstaticclassSolution1 { |
42 | 11 | publicintevalRPN(String[]tokens) { |
43 | | -Stack<String>stack =newStack<>(); |
44 | | -Set<String>op =newHashSet(); |
45 | | -op.add("+"); |
46 | | -op.add("-"); |
47 | | -op.add("*"); |
48 | | -op.add("/"); |
49 | | - |
50 | | -intexp =0; |
51 | | -Stringoperand1 =""; |
52 | | -Stringoperand2 =""; |
53 | | -for (inti =0;i <tokens.length; ) { |
54 | | -while ((i <tokens.length) && (!op.contains(tokens[i]))) { |
55 | | -stack.push(tokens[i]); |
56 | | -i++; |
57 | | - } |
58 | | -if (i ==tokens.length) { |
59 | | -if (!stack.isEmpty()) { |
60 | | -returnInteger.parseInt(stack.pop()); |
61 | | - } |
62 | | - }elseif (op.contains(tokens[i])) { |
63 | | -if (!stack.isEmpty()) { |
64 | | -operand2 =stack.pop(); |
65 | | - } |
66 | | -if (!stack.isEmpty() && !op.contains(stack.peek())) { |
67 | | -operand1 =stack.pop(); |
68 | | - } |
69 | | -if (tokens[i].equals("+")) { |
70 | | -exp =Integer.parseInt(operand1) +Integer.parseInt(operand2); |
71 | | - }elseif (tokens[i].equals("-")) { |
72 | | -exp =Integer.parseInt(operand1) -Integer.parseInt(operand2); |
73 | | - }elseif (tokens[i].equals("*")) { |
74 | | -exp =Integer.parseInt(operand1) *Integer.parseInt(operand2); |
75 | | - }elseif (tokens[i].equals("/")) { |
76 | | -exp =Integer.parseInt(operand1) /Integer.parseInt(operand2); |
| 12 | +Set<String>operators =newHashSet<>(Arrays.asList("+","-","*","/")); |
| 13 | +Stack<Integer>stack =newStack<>(); |
| 14 | +for (Stringtoken :tokens) { |
| 15 | +if (operators.contains(token)) { |
| 16 | +intsecondNum =stack.pop(); |
| 17 | +intfirstNum =stack.pop(); |
| 18 | +intresult; |
| 19 | +if (token.equals("+")) { |
| 20 | +result =firstNum +secondNum; |
| 21 | + }elseif (token.equals("-")) { |
| 22 | +result =firstNum -secondNum; |
| 23 | + }elseif (token.equals("*")) { |
| 24 | +result =firstNum *secondNum; |
77 | 25 | }else { |
78 | | -exp =Integer.parseInt(operand2); |
| 26 | +result =firstNum /secondNum; |
79 | 27 | } |
80 | | -stack.push(String.valueOf(exp)); |
81 | | -i++; |
| 28 | +stack.push(result); |
| 29 | + }else { |
| 30 | +intnum =Integer.parseInt(token); |
| 31 | +stack.push(num); |
82 | 32 | } |
83 | 33 | } |
84 | | -returnInteger.parseInt(stack.pop()); |
| 34 | +returnstack.pop(); |
85 | 35 | } |
86 | 36 | } |
87 | 37 | } |