Skip to content

Commit 5ce236c

Browse files
onlyliuxinonlyliuxin
authored
Merge pull request onlyliuxin#189 from wizardzhang2017/master
JVM第五次作业
2 parents d52c59a + 22e1be0 commit 5ce236c

File tree

140 files changed

+4229
-191
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

140 files changed

+4229
-191
lines changed

‎group27/383117348/.classpath

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,8 @@
11
<?xml version="1.0" encoding="UTF-8"?>
22
<classpath>
3-
<classpathentry kind="src" path="src"/>
3+
<classpathentry kind="src" path="data-structure"/>
44
<classpathentry kind="src" path="lib"/>
5+
<classpathentry kind="src" path="mini-jvm"/>
56
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/>
67
<classpathentry kind="lib" path="lib/junit.jar"/>
78
<classpathentry kind="lib" path="lib/org.hamcrest.core_1.3.0.v201303031735.jar"/>

‎group27/383117348/src/com/coderising/download/DownloadThread.java renamed to ‎group27/383117348/data-structure/com/coderising/download/DownloadThread.java

File renamed without changes.

‎group27/383117348/src/com/coderising/download/FileDownloader.java renamed to ‎group27/383117348/data-structure/com/coderising/download/FileDownloader.java

File renamed without changes.

‎group27/383117348/src/com/coderising/download/FileDownloaderTest.java renamed to ‎group27/383117348/data-structure/com/coderising/download/FileDownloaderTest.java

File renamed without changes.

‎group27/383117348/src/com/coderising/download/api/Connection.java renamed to ‎group27/383117348/data-structure/com/coderising/download/api/Connection.java

File renamed without changes.

‎group27/383117348/src/com/coderising/download/api/ConnectionException.java renamed to ‎group27/383117348/data-structure/com/coderising/download/api/ConnectionException.java

File renamed without changes.

‎group27/383117348/src/com/coderising/download/api/ConnectionManager.java renamed to ‎group27/383117348/data-structure/com/coderising/download/api/ConnectionManager.java

File renamed without changes.

‎group27/383117348/src/com/coderising/download/api/DownloadListener.java renamed to ‎group27/383117348/data-structure/com/coderising/download/api/DownloadListener.java

File renamed without changes.

‎group27/383117348/src/com/coderising/download/impl/ConnectionImpl.java renamed to ‎group27/383117348/data-structure/com/coderising/download/impl/ConnectionImpl.java

File renamed without changes.

‎group27/383117348/src/com/coderising/download/impl/ConnectionManagerImpl.java renamed to ‎group27/383117348/data-structure/com/coderising/download/impl/ConnectionManagerImpl.java

File renamed without changes.

‎group27/383117348/src/com/coderising/litestruts/LoginAction.java renamed to ‎group27/383117348/data-structure/com/coderising/litestruts/LoginAction.java

File renamed without changes.

‎group27/383117348/src/com/coderising/litestruts/Struts.java renamed to ‎group27/383117348/data-structure/com/coderising/litestruts/Struts.java

File renamed without changes.

‎group27/383117348/src/com/coderising/litestruts/StrutsTest.java renamed to ‎group27/383117348/data-structure/com/coderising/litestruts/StrutsTest.java

File renamed without changes.

‎group27/383117348/src/com/coderising/litestruts/View.java renamed to ‎group27/383117348/data-structure/com/coderising/litestruts/View.java

File renamed without changes.

‎group27/383117348/src/com/coderising/litestruts/struts.xml renamed to ‎group27/383117348/data-structure/com/coderising/litestruts/struts.xml

File renamed without changes.

‎group27/383117348/src/com/coding/basic/BinaryTreeNode.java renamed to ‎group27/383117348/data-structure/com/coding/basic/BinaryTreeNode.java

File renamed without changes.

‎group27/383117348/src/com/coding/basic/Iterator.java renamed to ‎group27/383117348/data-structure/com/coding/basic/Iterator.java

File renamed without changes.

‎group27/383117348/src/com/coding/basic/List.java renamed to ‎group27/383117348/data-structure/com/coding/basic/List.java

File renamed without changes.

‎group27/383117348/src/com/coding/basic/array/ArrayList.java renamed to ‎group27/383117348/data-structure/com/coding/basic/array/ArrayList.java

File renamed without changes.

‎group27/383117348/src/com/coding/basic/array/ArrayUtil.java renamed to ‎group27/383117348/data-structure/com/coding/basic/array/ArrayUtil.java

File renamed without changes.

‎group27/383117348/src/com/coding/basic/linklist/LRUPageFrame.java renamed to ‎group27/383117348/data-structure/com/coding/basic/linklist/LRUPageFrame.java

File renamed without changes.

‎group27/383117348/src/com/coding/basic/linklist/LRUPageFrameTest.java renamed to ‎group27/383117348/data-structure/com/coding/basic/linklist/LRUPageFrameTest.java

File renamed without changes.

‎group27/383117348/src/com/coding/basic/linklist/LinkedList.java renamed to ‎group27/383117348/data-structure/com/coding/basic/linklist/LinkedList.java

File renamed without changes.

‎group27/383117348/data-structure/com/coding/basic/queue/CircleQueue.java

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
package com.coding.basic.queue;
2+
3+
public class CircleQueue {
4+
5+
}

‎group27/383117348/data-structure/com/coding/basic/queue/Josephus.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.coding.basic.queue;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* 用Queue来实现Josephus问题 在这个古老的问题当中， N个深陷绝境的人一致同意用这种方式减少生存人数： N个人围成一圈（位置记为0到N-1），
8+
* 并且从第一个人报数， 报到M的人会被杀死， 直到最后一个人留下来
9+
*
10+
* @author liuxin
11+
*
12+
*/
13+
public class Josephus {
14+
15+
public static List<Integer> execute(int n, int m) {
16+
if (n < m || n <= 0 || m <= 0) {
17+
throw new RuntimeException("传入参数有误,执行失败!");
18+
}
19+
//保存被杀掉的数
20+
List<Integer> ints = new ArrayList<Integer>();
21+
//报数
22+
int count = 0;
23+
while(ints.size()!=n){
24+
25+
for(int i=0;i<n;i++){
26+
count++;
27+
if(count==m){
28+
ints.add(i);
29+
count = 0;
30+
}
31+
}
32+
33+
}
34+
return ints;
35+
}
36+
37+
public static void main(String[] args) {
38+
List<Integer> list = execute(7, 2);
39+
System.out.println(list);
40+
}
41+
42+
}

‎group27/383117348/data-structure/com/coding/basic/queue/JosephusTest.java

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package com.coding.basic.queue;
2+
import org.junit.After;
3+
import org.junit.Assert;
4+
import org.junit.Before;
5+
import org.junit.Test;
6+
7+
8+
9+
public class JosephusTest {
10+
11+
@Before
12+
public void setUp() throws Exception {
13+
}
14+
15+
@After
16+
public void tearDown() throws Exception {
17+
}
18+
19+
@Test
20+
public void testExecute() {
21+
22+
Assert.assertEquals("[1, 3, 5, 0, 4, 2, 6]", Josephus.execute(7, 2).toString());
23+
24+
}
25+
26+
}

‎group27/383117348/src/com/coding/basic/Queue.java renamed to ‎group27/383117348/data-structure/com/coding/basic/queue/Queue.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.coding.basic;
1+
package com.coding.basic.queue;
22

33
import org.junit.Test;
44

‎group27/383117348/data-structure/com/coding/basic/queue/QueueWithTwoStacks.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.coding.basic.queue;
2+
import java.util.Stack;
3+
4+
public class QueueWithTwoStacks<E> {
5+
private Stack<E> stack1;
6+
private Stack<E> stack2;
7+
8+
9+
public QueueWithTwoStacks() {
10+
stack1 = new Stack<E>();
11+
stack2 = new Stack<E>();
12+
}
13+
14+
15+
16+
17+
public boolean isEmpty() {
18+
return false;
19+
}
20+
21+
22+
23+
public int size() {
24+
return -1;
25+
}
26+
27+
28+
29+
public void enQueue(E item) {
30+
31+
}
32+
33+
public E deQueue() {
34+
return null;
35+
}
36+
37+
38+
}

‎group27/383117348/src/com/coding/basic/stack/Stack.java renamed to ‎group27/383117348/data-structure/com/coding/basic/stack/Stack.java

File renamed without changes.

‎group27/383117348/src/com/coding/basic/stack/StackUtil.java renamed to ‎group27/383117348/data-structure/com/coding/basic/stack/StackUtil.java

File renamed without changes.

‎group27/383117348/data-structure/com/coding/basic/stack/expr/InfixExpr.java

Lines changed: 181 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,181 @@
1+
package com.coding.basic.stack.expr;
2+
3+
import java.util.ArrayList;
4+
5+
import com.coding.basic.stack.Stack;
6+
import com.coding.basic.stack.StackUtil;
7+
8+
public class InfixExpr {
9+
private String expr = null;
10+
11+
public InfixExpr(String expr) {
12+
this.expr = expr;
13+
}
14+
/**
15+
* 对expr进行解析计算
16+
* @return
17+
*/
18+
public float evaluate() {
19+
float f = 0.0f;
20+
//如果不为空继续解析
21+
if (expr != null || expr.length() > 0) {
22+
//如果符号不对称,抛出异常
23+
if (!StackUtil.isValidPairs(expr)) {
24+
try {
25+
throw new Exception("格式不正确,解析表达式失败!");
26+
} catch (Exception e) {
27+
e.printStackTrace();
28+
}
29+
};
30+
//将字符串转化为集合
31+
ArrayList<String> list=getStringList(expr);
32+
//根据获得的集合转化为后序表达式集合
33+
ArrayList<String> postOrder = getPostOrder(list);
34+
Stack stack = new Stack();
35+
for (int i = 0; i < postOrder.size(); i++) {
36+
//如果为数字,则压入栈
37+
if(Character.isDigit(postOrder.get(i).charAt(0))){
38+
stack.push(Float.parseFloat(postOrder.get(i)));
39+
}else{
40+
//否则,取出栈顶两个元素进行计算.
41+
Float back = (Float)stack.pop();
42+
Float front = (Float)stack.pop();
43+
Float res = 0.0f;
44+
switch (postOrder.get(i).charAt(0)) {
45+
case '+':
46+
res = front + back;
47+
break;
48+
case '-':
49+
res = front - back;
50+
break;
51+
case '*':
52+
res = front * back;
53+
break;
54+
case '/':
55+
res = front / back;
56+
break;
57+
}
58+
//将结果再压回栈中
59+
stack.push(res);
60+
}
61+
}
62+
//最终计算结果出栈;
63+
f = (Float)stack.pop();
64+
65+
} else {
66+
//为空抛出异常
67+
try {
68+
throw new Exception("表达式内容为空,解析失败!");
69+
} catch (Exception e) {
70+
// TODO Auto-generated catch block
71+
e.printStackTrace();
72+
}
73+
}
74+
return f;
75+
}
76+
/**
77+
* 将字符串转换为集合方法
78+
* @param str
79+
* @return
80+
*/
81+
private ArrayList<String> getStringList(String str) {
82+
ArrayList<String> result = new ArrayList<String>();
83+
String num = "";
84+
for (int i = 0; i < str.length(); i++) {
85+
//如果为数字,叠加到num字符串中
86+
if (Character.isDigit(str.charAt(i))) {
87+
num = num + str.charAt(i);
88+
} else {
89+
//如果num不为空,表示数字字符凑够了,加到集合里
90+
if (num != "") {
91+
result.add(num);
92+
}
93+
//然后再把非数字字符也加到集合中,清空num字符串
94+
result.add(str.charAt(i) + "");
95+
num = "";
96+
}
97+
}
98+
//最后判断下,num中还有值没,有的话加到集合里
99+
if (num != "") {
100+
result.add(num);
101+
}
102+
//返回结果
103+
return result;
104+
}
105+
106+
/**
107+
* 中序表达式转后序表达式
108+
* @param list
109+
* @return
110+
*/
111+
private ArrayList<String> getPostOrder(ArrayList<String> list) {
112+
113+
ArrayList<String> result = new ArrayList<String>();
114+
Stack stack = new Stack();
115+
for (int i = 0; i < list.size(); i++) {
116+
//如果为数字,加到集合里
117+
if (Character.isDigit(list.get(i).charAt(0))) {
118+
result.add(list.get(i));
119+
} else {
120+
switch (list.get(i).charAt(0)) {
121+
//如果有左括号,先压入操作符栈中
122+
case '(':
123+
stack.push(list.get(i));
124+
break;
125+
//ok,等到右括号了
126+
case ')':
127+
//先看看操作符栈顶是不是左括号头头
128+
while (!stack.peek().equals("(")) {
129+
//不是左括号头头,就把操作符栈中的操作符弹出来一个,加到集合里,一直弹到见到左括号为止
130+
result.add((String) stack.pop());
131+
}
132+
//最后把左括号也弹出来,这样就只有加减乘除没有括号了
133+
stack.pop();
134+
break;
135+
default:
136+
//这里全是处理加减乘除的操作
137+
//如果操作符栈不为空,比较下当前操作符和操作符栈顶的操作符优先级大小
138+
while (!stack.isEmpty() && compare((String) stack.peek(), list.get(i))) {
139+
//如果栈顶操作符优先级大于当前,则栈中的操作符弹出加到集合里
140+
result.add((String) stack.pop());
141+
}
142+
//否则继续压到栈中,或者之前栈中元素已经弹出,再将优先级小的操作符加到操作符栈中.
143+
stack.push(list.get(i));
144+
break;
145+
}
146+
}
147+
}
148+
while (!stack.isEmpty()) {
149+
//最后看下操作符栈还有操作符没,有了加到集合末尾
150+
result.add((String) stack.pop());
151+
}
152+
return result;
153+
}
154+
/**
155+
* 操作符优先级比较算法
156+
* @param peek
157+
* @param cur
158+
* @return
159+
*/
160+
public static boolean compare(String peek, String cur) {
161+
//乘除优先级大于加减
162+
//如果操作符栈顶操作符的优先级大于当前操作符的优先级,则返回true
163+
if ("*".equals(peek) && ("/".equals(cur) || "*".equals(cur) || "+".equals(cur) || "-".equals(cur))) {
164+
return true;
165+
} else if ("/".equals(peek) && ("/".equals(cur) || "*".equals(cur) || "+".equals(cur) || "-".equals(cur))) {
166+
return true;
167+
} else if ("+".equals(peek) && ("+".equals(cur) || "-".equals(cur))) {
168+
return true;
169+
} else if ("-".equals(peek) && ("+".equals(cur) || "-".equals(cur))) {
170+
return true;
171+
}
172+
//如果当前操作符的优先级大于栈顶的操作符优先级,返回false
173+
return false;
174+
}
175+
176+
public static void main(String[] args) {
177+
InfixExpr expr = new InfixExpr("3*20+13*5-40/2");
178+
float f = expr.evaluate();
179+
System.out.println(f);
180+
}
181+
}

‎group27/383117348/data-structure/com/coding/basic/stack/expr/InfixExprTest.java

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package com.coding.basic.stack.expr;
2+
3+
import org.junit.After;
4+
import org.junit.Assert;
5+
import org.junit.Before;
6+
import org.junit.Test;
7+
8+
public class InfixExprTest {
9+
@Before
10+
public void setUp() throws Exception {
11+
}
12+
13+
@After
14+
public void tearDown() throws Exception {
15+
}
16+
17+
@Test
18+
public void testEvaluate() {
19+
//InfixExpr expr = new InfixExpr("300*20+12*5-20/4");
20+
{
21+
InfixExpr expr = new InfixExpr("2+3*4+5");
22+
Assert.assertEquals(19.0, expr.evaluate(), 0.001f);
23+
}
24+
{
25+
InfixExpr expr = new InfixExpr("3*20+12*5-40/2");
26+
Assert.assertEquals(100.0, expr.evaluate(), 0.001f);
27+
}
28+
29+
{
30+
InfixExpr expr = new InfixExpr("3*20/2");
31+
Assert.assertEquals(30, expr.evaluate(), 0.001f);
32+
}
33+
34+
{
35+
InfixExpr expr = new InfixExpr("20/2*3");
36+
Assert.assertEquals(30, expr.evaluate(), 0.001f);
37+
}
38+
39+
{
40+
InfixExpr expr = new InfixExpr("10-30+50");
41+
Assert.assertEquals(30, expr.evaluate(), 0.001f);
42+
}
43+
44+
}
45+
46+
}

0 commit comments

Comments
 (0)