Skip to content

Commit 0b369d3

Browse files
fishercoder1534fishercoder1534
committed
add 1628
1 parent a779a8b commit 0b369d3

File tree

3 files changed

+139
-0
lines changed

3 files changed

+139
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -182,6 +182,7 @@ _If you like this project, please leave me a star._ ★
182182
|1636|[Sort Array by Increasing Frequency](https://leetcode.com/problems/sort-array-by-increasing-frequency/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1636.java) ||Easy|Array, Sort|
183183
|1630|[Arithmetic Subarrays](https://leetcode.com/problems/arithmetic-subarrays/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1630.java) ||Medium|Sort|
184184
|1629|[Slowest Key](https://leetcode.com/problems/slowest-key/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1629.java) ||Easy|Array|
185+
|1628|[Design an Expression Tree With Evaluate Function](https://leetcode.com/problems/design-an-expression-tree-with-evaluate-function/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1628.java) ||Medium|Stack, Binary Tree, Design, Math|
185186
|1626|[Best Team With No Conflicts](https://leetcode.com/problems/best-team-with-no-conflicts/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1626.java) ||Medium|DP|
186187
|1625|[Lexicographically Smallest String After Applying Operations](https://leetcode.com/problems/lexicographically-smallest-string-after-applying-operations/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1625.java) ||Medium|BFS, DFS|
187188
|1624|[Largest Substring Between Two Equal Characters](https://leetcode.com/problems/largest-substring-between-two-equal-characters/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1624.java) |[:tv:](https://youtu.be/rfjeFs3JuYM)|Easy|String|

‎src/main/java/com/fishercoder/solutions/_1628.java

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.Deque;
4+
import java.util.LinkedList;
5+
import java.util.List;
6+
7+
public class _1628 {
8+
public static class Solution1 {
9+
/**
10+
* Being able to think of resorting to Stack data structure is the key here to a straightforward solution.
11+
*/
12+
13+
public abstract static class Node {
14+
public abstract int evaluate();
15+
16+
public abstract List<String> print(Node node, List<String> list);
17+
18+
// define your fields here
19+
Node left;
20+
Node right;
21+
String val;
22+
}
23+
24+
static class NodeImpl extends Node {
25+
26+
@Override
27+
public int evaluate() {
28+
return inorder(this);
29+
}
30+
31+
private int inorder(Node node) {
32+
if (node == null) {
33+
return 0;
34+
}
35+
if (node.left == null && node.right == null) {
36+
return Integer.parseInt(node.val);
37+
}
38+
String op = node.val;
39+
int left = inorder(node.left);
40+
int right = inorder(node.right);
41+
if (op.equals("+")) {
42+
return left + right;
43+
} else if (op.equals("-")) {
44+
return left - right;
45+
} else if (op.equals("*")) {
46+
return left * right;
47+
} else {
48+
return left / right;
49+
}
50+
}
51+
52+
public NodeImpl(String val) {
53+
this.val = val;
54+
}
55+
56+
@Override
57+
public List<String> print(Node node, List<String> list) {
58+
if (node == null) {
59+
return list;
60+
}
61+
print(node.left, list);
62+
list.add(node.val);
63+
print(node.right, list);
64+
return list;
65+
}
66+
67+
}
68+
69+
public static class TreeBuilder {
70+
public Node buildTree(String[] postfix) {
71+
Deque<Node> stack = new LinkedList<>();
72+
for (String str : postfix) {
73+
Node node = new NodeImpl(str);
74+
if (!Character.isDigit(str.charAt(0))) {
75+
node.right = stack.pollLast();
76+
node.left = stack.pollLast();
77+
}
78+
stack.addLast(node);
79+
}
80+
return stack.pop();
81+
}
82+
83+
}
84+
}
85+
}

‎src/test/java/com/fishercoder/_1628Test.java

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.utils.CommonUtils;
4+
import com.fishercoder.solutions._1628;
5+
import org.junit.BeforeClass;
6+
import org.junit.Test;
7+
8+
import java.util.ArrayList;
9+
import java.util.List;
10+
11+
import static org.junit.Assert.assertEquals;
12+
13+
public class _1628Test {
14+
private static _1628.Solution1.TreeBuilder treeBuilderSolution1;
15+
16+
@BeforeClass
17+
public static void setup() {
18+
treeBuilderSolution1 = new _1628.Solution1.TreeBuilder();
19+
}
20+
21+
@Test
22+
public void test1() {
23+
_1628.Solution1.Node node = treeBuilderSolution1.buildTree(new String[]{"3", "4", "+"});
24+
List<String> list = node.print(node, new ArrayList<>());
25+
CommonUtils.printList(list);
26+
assertEquals(7, node.evaluate());
27+
}
28+
29+
@Test
30+
public void test2() {
31+
_1628.Solution1.Node node = treeBuilderSolution1.buildTree(new String[]{"3", "4", "+", "2", "*", "7", "/"});
32+
List<String> list = node.print(node, new ArrayList<>());
33+
CommonUtils.printList(list);
34+
assertEquals(2, node.evaluate());
35+
}
36+
37+
@Test
38+
public void test3() {
39+
_1628.Solution1.Node node = treeBuilderSolution1.buildTree(new String[]{"4", "5", "2", "7", "+", "-", "*"});
40+
List<String> list = node.print(node, new ArrayList<>());
41+
CommonUtils.printList(list);
42+
assertEquals(-16, node.evaluate());
43+
}
44+
45+
@Test
46+
public void test4() {
47+
_1628.Solution1.Node node = treeBuilderSolution1.buildTree(new String[]{"4", "2", "+", "3", "5", "1", "-", "*", "+"});
48+
List<String> list = node.print(node, new ArrayList<>());
49+
CommonUtils.printList(list);
50+
assertEquals(18, node.evaluate());
51+
}
52+
53+
}

0 commit comments

Comments
 (0)