▶ 书中第一章部分程序，加上自己补充的代码，包括简单的计时器，链表背包迭代器，表达式计算相关
● 简单的计时器，分别记录墙上时间和 CPU 时间。
package package01; import java.lang.management.ThreadMXBean;
import java.lang.management.ManagementFactory; public class class01
{
private final ThreadMXBean threadTimer; // CPU 计时器
private final long startWall; // 墙上时间
private final long startCPU; // CPU 时间 public class01() // 构造函数即开始计时
{
startWall = System.currentTimeMillis();
threadTimer = ManagementFactory.getThreadMXBean();
startCPU = threadTimer.getCurrentThreadCpuTime();
} public void elapsedTime() // 停止计时并输出结果
{
long finishWall = System.currentTimeMillis();
long finishCPU = threadTimer.getCurrentThreadCpuTime();
System.out.printf("Wall time: %d ms, CPU time:%d ns\n", finishWall - startWall, finishCPU - startCPU);
} public static void main(String[] args)
{
class01 clock = new class01(); double sum = 0.0;
for (int i = 1; i <= 100000000; i++)
sum += Math.pow(i, 0.5); clock.elapsedTime();
}
}
● 在链表背包数据结构的基础上实现迭代器
package package01; import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import java.util.Iterator;
import java.util.NoSuchElementException; public class class01<Item> implements Iterable<Item>
{
private Node<Item> first; // 头节点
private int n; // 物品数 private static class Node<Item> // 链表结构
{
private Item item;
private Node<Item> next;
} public class01()
{
first = null;
n = 0;
} public boolean isEmpty()
{
return first == null;
} public int size()
{
return n;
} public void add(Item item)
{
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
n++;
} public Iterator<Item> iterator() // 实现迭代器
{
return new ListIterator<Item>(first);
} private class ListIterator<Item> implements Iterator<Item> // 迭代器的基本结构
{
private Node<Item> current;
public ListIterator(Node<Item> first)
{
current = first;
} public boolean hasNext()
{
return current != null;
}
public void remove() // 不含 remove() 方法
{
throw new UnsupportedOperationException();
} public Item next()
{
if (!hasNext())
throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
} public static void main(String[] args)
{
class01<String> bag = new class01<String>();
while (!StdIn.isEmpty())
{
String item = StdIn.readString();
bag.add(item);
} StdOut.println("size of bag = " + bag.size());
for (String s : bag) {
StdOut.println(s);
}
}
}
■ 输入输出要点，在这里使用了 algs4 的 StdIn，需要给出多行的程序输入（用 "<" 重定向的不用考虑这部分）。在命令行中执行 java XXX 后逐行输入，用回车键隔开，全部输入完后回车到新的一行，按 Ctrl + z 结束输入程序自动向下运行；而在 IntelliJ中，点击执行后逐行输入，用回车键隔开，全部输入完后回车到新的一行，按 Ctrl + d 结束输入程序自动向下运行
● 表达式计算相关
package package01; import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdIn; public class class01
{
public static double evaluate(String args) // Dijkstra 双栈中缀表达式计算
{
Stack<String> ops = new Stack<String>(); // 算符栈
Stack<Double> vals = new Stack<Double>(); // 操作数栈 for (int i = 0; i<args.length(); i++)
{
String s = args.charAt(i) + ""; if (s.equals("(") || s.equals(" ")) // 跳过左括号和空格
;
else if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("sqrt")) // 运算符，压栈
ops.push(s);
else if (s.equals(")")) // 右括号，吐栈并计算
{
String op = ops.pop();
double v = vals.pop(); if (op.equals("+"))
v = vals.pop() + v;
else if (op.equals("-"))
v = vals.pop() - v;
else if (op.equals("*"))
v = vals.pop()*v;
else if (op.equals("/"))
v = vals.pop() / v;
else if (op.equals("sqrt"))
v = Math.sqrt(v); vals.push(v); // 数字压栈，缺点是只能读取一位数字
}
else vals.push(Double.parseDouble(s)); // 计算结果压栈
}
return vals.pop();
} public static String correctBracket(String[] args) // P102, Ex1.3.9，将中缀表达式缺失的左括号补全
{
Stack<String> ops = new Stack<String>();
Stack<String> vals = new Stack<String>(); for (; !StdIn.isEmpty();)
{
String s = StdIn.readString(); if (s.equals("(") || s.equals(" ")) // 左括号，不作任何操作
;
if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("sqrt")) // 运算符，压栈
ops.push(s);
else if (s.equals(")")) // 右括号，吐栈
{
String op = ops.pop();
String v = vals.pop();
if (op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/"))
v = String.format("( %s %s %s )", vals.pop(), op, v);
else if (op.equals("sqrt"))
v = String.format("( %s ( %s ) )", op, v); vals.push(v);
}
else vals.push(s);
//else vals.push(((Double)Double.parseDouble(s)).toString()); // 输出浮点数的情况
}
return vals.pop();
} public static void main(String[] args)// 测试输入：1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )
{
String output1 = correctBracket(args);
double output2 = evaluate(output1);
System.out.printf("%s\n%f\n", output1, output2);
}
}