今日学习内容

算术表达式求值类

昨天写了算术表达式求值程序 Evaluate类。它在 《算法》书的例子上加了解析 Token 的内容 (parseToken 函数)。

parseToken 只是简单地解析算术表达式的 Token 流，并不判断表达式的正确性，如果遇到了关键字错误(sqrt 写错)，程序会直接抛出异常。如果算数表达式写的不对，例如括号匹配不上，Evaluate类也不会抛出异常，所以这不是一个编译器，只是一个简单的求值算法。

自动扩容的栈

今天写了一个简单的可以自动扩容的栈 ResizingArrayStack。程序比较简单，有意思的是选择缩容的时间点。

缩容时机 缩容的大小 缩容后栈的容量 可能的坏处
1/2 1/2 100% push 元素会导致再次扩容
1/3 1/2 66.7% 缩容后的栈偏满，push 容易出发扩容
1/4 1/2 50% 无
1/5 1/2 40% 缩容时机的条件较小，不容易触发，这样容易让栈很大，浪费空间
… … … 1/5 后的缩容条件和 1/5 的问题相同

这里比较了缩容大小是 1/2 时，各种缩容时机的比较，发现 1/4 是最合适的缩容时机，其他的都显得不合适。