今日学习内容

今天阅读了《算法》的 1.3.1 节和 1.3.2 节。

集合，队列和栈

这两节讲述了三种数据结构，集合，队列，和栈。

集合中的数据无序，主要 API 是判断元素是否在集合中。

队列是一种先进先出的数据结构，主要 API 是入队和出队 enqueue， dequeue

栈是一种后进先出的数据结构，主要 API 是压栈和弹栈 push, pop

Dijkstra 双栈算数表达式求值法

这个算法主要用于算术表达式的求值

例如如下表达式: ( 1 + (5 * 20))

它的思路是创建两个栈，操作数栈和运算符栈，挨个读入表达式的 token,

  • 将操作数压入操作数栈
  • 将运算符压入运算符栈
  • 忽略左括号
  • 遇到右括号时，弹出一个运算符，弹出所需数量的操作数，将运算符和操作数的运算结果压入操作数栈。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

public class Evaluate {
    public static void main(String[] args) {
        Stack<String> operator = new Stack<>();
        Stack<Double> value = new Stack<>();
        while (!StdIn.isEmpty()) {
            String s = StdIn.readString();
            if (s.equals("(")) {
                ;
            } else if (s.equals("+")) {
                operator.push(s);
            } else if (s.equals("-")) {
                operator.push(s);
            } else if (s.equals("*")) {
                operator.push(s);
            } else if (s.equals("/")) {
                operator.push(s);
            } else if (s.equals("sqrt")) {
                operator.push(s);
            } else if (s.equals(")")) {
                String op = operator.pop();
                double v = value.pop();
                if (op.equals("+")) {
                    v = value.pop() + v;
                } else if (op.equals("-")) {
                    v = value.pop() - v;
                } else if (op.equals("*")) {
                    v = value.pop() * v;
                } else if (op.equals("/")) {
                    v = value.pop() / v;
                } else if (op.equals("sqrt")) {
                    v = Math.sqrt(v);
                }
                value.push(v);
            } else {
                value.push(Double.parseDouble(s));
            }
        }
        StdOut.println(value.pop());
    }
}

计算样本标准差和平均值

今天从习题中学到一种计算平均值和样本标准差的新办法，原理还没理解，先记录下来

  • 数学定义:

平均值

$$ \bar{x} = \frac{[x_1+x_2+ \dots + x_n]}{n} $$

样本标准差

$$ s = \sqrt {\frac{(x_1-\bar{x})^2+(x_2-\bar{x})^2+\cdots+(x_n-\bar{x})^2}{n-1}} \ = \sqrt{\frac{1}{n-1} \displaystyle \sum^n_{i=1}(x_i-\bar{x})^2} $$

样本标准差是使用样本计算的值来估计整体，为了更接近整体，它做了一些校正，将除N改成了除N-1。这叫 贝塞尔无偏估计校正系数

  • 计算程序

代码见 Github，它的核心代码是下面这三行

1
2
3
4
5
6
7
8

// N 表示输入的数字的数量
// mean 表示根据输入数字计算出的平均值
// sqrt(s / N-1) 表示当前输入数字的样本标准差
public void AddNumber(Integer x) {
    N++;
    s = s + 1.0 * (N - 1) / N * (x - mean) * (x - mean);
    mean = mean + (x - mean) / N;
}

上面这种计算方法使得我们可以用流式的方法来计算平均值和样本标准差，输入多少，计算多少，不用读取全部数字就可以计算。

参考链接