所以说了这么多，我们谈谈怎么用Kotlin写计算器吧……（也就是我要引入这次用小技巧来优化的递归算法）

计算器很简单：

Expr = AddSub
AddSub = MulDiv [+-] MulDiv
MulDiv = <int> [*/] <int>

这里为了方便我们不使用scannerless parsing的风格…… <int> 表示它是一个有状态存储的 Token 的意思，而 for、void 这种就是『无状态存储』的 Token。
（不知道是不是有点不良实践了，emmm）
Scanner: java.util.Scanner.

为了节省时间我只写一个复用抽提程度比较低的版本：

import java.lang.System
import java.util.Scanner as Lex

val input = Lex(System.`in`, "UTF8") //.useDelimiter("[\\+\\-\\*/]") // 好吧，我才知道delimiter不会next给你
//... 鉴于Java Scanner实在是太过弱鸡，暂时不支持不加空格的情况。

typealias Join = (Int, Int) -> Int
/** [prec]: Ascending order */
enum class Op(val prec: Int, val join: Join) {
  `*`(0, {a,b->a*b}), `$`(0, {a,b->a/b}),
  `+`(1, {a,b->a+b}), `-`(1, {a,b->a-b})
}
// 不准吐槽骚 Op 定义法…… 不过由于 `/` 这个名字依然是非法的（下文必须用到 Enum 类上自动生成的valueOf String），所以这里暂时通融一下，($)=(/)。

object Calculator {
  val terminateKw = "." //同样是一个通融，因为计算器很简单不好选择中缀链的终止符号(也可以选EOF但我不喜欢)，为了方便起见选择这个
  // 1 + 2 * 3 .
  @JvmStatic fun main(vararg arg: String) {
    scanInt().let(::infixChain).let(::println)
  }
  // 鉴于单纯LL1无法处理两个字符的中缀算符，
  // 为了优雅性不得不把上一次为了比较结合顺序的算符解析结果传来传去的
  // 不过如果没有也不影响
  private fun infixChain(base: Int, op_left: Op? = null): Int {
    val op1 = op_left ?: scanInfix() // '+'
    val rhs1 = scanInt()
    val op2 = scanInfix() // '*'
    return when {
      op1.prec <= op2.prec -> infixChain(op1.join(base, rhs1), op2) //(1+2)*3, 没事
      op1.prec  > op2.prec -> op1.join(base, infixChain(rhs1, op2)) //1+(2*3), 被人抢跑咯~
    }
  }
  private fun scanInt() = input.nextInt()
  private fun scanInfix() = Op.valueOf(input.next())
}

(大意，可编译版本过会发文件)

这里我们使用了『上下文相关』（个🍺）解析法…… 算了其实是无关，但是有这样的优化。
所谓的上下文就是 base, op1, rhs1, op2 啦，其实也不能算上下文，它就是见机行事好然解析过程更高效而已
这个解析算法算是经典的递归下降…… 不是很好理解吧？不如上面好理解吧？这就对了……
想想它是怎么解析 1 + 2 * 3 + 1 . 的，递归调用是这样，其他自己想吧：

scan(1, null) 

//op1=(+), rhs1=2, op2=(*)

  scan(2, `*`) 

//op1=(*), rhs1=3, op2=(+)

  scan(6, `+`) 

//op1=(+), rhs1=1, rhs2=[done]
//return (+) 6 1
//return (+) 1 7
就是这样，那么又有什么可以优化的呢？？？

不是能力下降……不是能力下降…… 是我的IDEA最近Tasks有点毛了，改代码总是忘记重新编译，造成各种古怪问题行号不对称后来才发现

最近手越来越生了，Peek(Iterator)里简单的时序都看不出来，consume()方法写错了，呵呵。

既然都这么弄了，还不如直接把优化写成代码算了……

这个是无优化版本的四则计算器

所以先梗概一下：其实这个所谓的优化就是显式的递归栈。

我们知道这个二元链解析器是这么工作的：

1+^2*3

每层我们都结合一个中缀[(a+b)什么的]。我们扫描到^的时候，会向前看一个中缀，目的是判断rhs1(这里的"2")该和谁结合
+ 如果 (+) 的优先级大，(1+2)
+ 否则(*)的优先级大，1+ (2*...)
注意上面的， (2 * ...) 这已经暴露了递归子程序需要的参数了：一个是 base (左边的那个表达式)、一个是 (*) 运算符
当它不是作为第一个解析器解析的时候，op_left 为空，就自动运行 scanInfix()，得到第一个 infix
当然也可能得不到，这是属于当前不是 infix 链的情况（一般所有的编程语言无论传统还是函数式还是啥子的，值基本都是表达式链表达的，所以也可能是一个单独的表达式）

在这个过程中，为了能够看到前面的一个op(op2)我们要多consume() 一个，但是这个很可能会失败。
举个例子，上面的 ...(2*3^) 扫描的时候就会找不到后面的op2，就必须返回 op1(base, rhs1) 的结果，而且你递归下去 infixChain(op1(base, rhs1)) 也不能少写这点代码，这是不可以省略的。

但是 rhs1 不可能失败，如果失败了就属于用户输入了 (1+) 这种不完整的中缀表达式。

所以怎么样呢？我想说，直接用数据栈而不是系统的调用栈建模递归会更高效一些。

比如说（当然是对于 1+(2*...) 这种等右结合的情况），这里我们为了保证递归回溯的时候能正常，不得不保留全部的栈帧变量：
+ base，op.join 的目标A
+ op1，op.join 的目标B
+ rhs1，这个已经非必须了
+ op2，这个也已经非必需了

其实这个栈帧的体积是可以缩小一半的（其实栈本来就应该是 [(1+), (2*3)] 这种形式）
然后我们利用面向对象的抽象，可以非常容易第弄出一个 Recursion<T> 数据结构，在上面用 mapTop 操作可以实现 tco、add 操作来增加入栈、reduce 来对 LIFO(LastInFirstOut) 进行归约就好了

return stack.reduce { x, r -> when (x) {
is Base -> x.expr
is Tail -> x.join(r)
} }
就可以鸟。

暂时只能写这么多了，写不出来鸟

少建了一处Base，不过不打紧，我明天改

只要智商不滑坡，方法总比问题多（跑

求心疼本苏身体的dalao帮忙补充

说起来，用显式栈也真是很长很麻烦，还是直白递归下降好

https://github.com/Netrvin/PageGuard.js

检测developer console打开状况的方法：
+ Function.toString + console.log
+ Regex.toString + console.log
+ Chrome console.profiles
+ window.innerHeight

不让复制的CSS：

* {
user-select: none;
-?-user-select: none;
}

input { -?-user-select: auto; }

@media print { * { display: none; } }

咱来说说为什么少了一个 base。

其实这个递归是非常有模式的，比如说，
在 infixChain1 里我们会提供 base 让它去扫，而不是什么都不加，仅仅遗忘自己刚才扫描的 rhs1

然后 infixChain 也一样
[(1 +), 2] 👈 这就是『新的base』
就是这样，喵。

现在这个程序是这个样子，咱来看看。

我们举一大堆输入示例，然后一步一步算。

1 — scanInfix() ?: return atomAt0
1 + 1 — op1=(+), [Base(1)], rhs1=1, [Base(+ join 1, 1)]
1 + 2 * 3 — op1=(+), [Base(1)], rhs1=2,
op2=(*), [Tail(1, (+)), Base(2)]
看到了吗？上面 ^
就是第一个『等待结合』的情况，我们又回到了「递归」的原点 — 一次递归扫描的开始
当然，这里我们的 tail 会直接 reduce 一次，显然它必须保证当前栈顶一定是 Base
这是可以保证的，因为我们在每次 push 上 Tail 的时候，都会接着 push 一个 Base，而第一次 push 的是一个 Base。

比如说，假设有 () 优先级大于 (*)，0 + 1 * 2 3 显然需要 [Tail(0 +), Tail(1 *), Base(2 3)] — 扫描 op1=() 的时候 scanInfix() 失败，于是它会直接开始规约过程
可是这个栈它是这么构造的：
[Base(0)]
[Tail(0 +), Base(1)] op1=(+), op2=(*)
[Tail(0 +), Tail(1 *), Base(2)] op1=(*), op2=()
[Tail(0 +), Tail(1 *), Base(2)] rhs1=3, op1=(), op2=fail
找不到比较的第二个参数，中缀链扫描完毕，开始回溯组织语法结构。

[Tail(0 +), Tail(1 *), Base(2 3)]
[Tail(0 +), Base(1* (2 3) )]
[Base(0 + (1* (2 ** 3)) )]

至于我要写成连 [Tail(...), Tail(...), Base(...)] 都兼容的模式，用reduce，是没道理的（因为相邻两项都会自然折叠好的……）。
好吧，其实是有道理的，这样会优雅一些（迫真）

进一步优化还可以用 JDK 的 Thread local storage，因为每个线程同时只能运行一个函数。
换句话说一个线程对 infixChain() 函数调用有一个栈就够了，用完 clear() 就可以，这是个存储分配方面的优化。
当然，如果你的那个 fun 是 suspend fun 当我没说

为了兼容性这个优化我没有做。

运行的时候就是这样

结合就是这样结合 (1 + 2 ^*)

然后你接着往下输入 +1, 到扫描下一个 infix 的时候它要阻塞等待输入

最后你要回溯的栈就是这样 (1 +) ((2 * 3) + 1)，得 8。

然后咱再来测试一下 0 + 1 * 2 ** 3 这种情况，假定 (**) 也是左结合的：
一确保算法在多个 Tail 同时出现的情况下（看起来）可以正常工作。