Literal-expression

literal-expression interceptor

背景

String作为表达式的输入源，实现简易的Interceptor/Decoder，需要通过PatternMatch维护状态机（比如栈），不同嵌套级别的ContextScope（比如Stack/Map），难度一般为Middle到Hard

比如

只涉及长度位置的问题，连Lexer都不用使用（Middle）
实现Tokenizer（用2个while）
实现一个计算器/Encoder/Decoder（Middle～Hard）(涉及乘法优先级的太恶心，我是不会搞的，反正这种公司也不去)
实现一个OGNL，模版引擎（支持，取属性与$取）（Hard）
支持赋值与函数的Lisp表达式处理器（ READ/EVAL/PRINT LOOP，Very Hard），可以参考Clojure的LispReader(注意它解析后S-Exp是放在表达式上下文运行的)

其中hard的占总hard的15%，很多问题是披着String的外表，内部却干着（简易）编译器的活。

常见解析流程

前三种问题均可以由下面流程搞定，注意，由于题目一般都是理想情况，因此为了时间并没有使用AST的DFS，仍然是String的startWith处理PatternMatch

步骤如下

初始化

如果涉及到env，进行Runtime的init

Atomic处理

对于无法拆分的Atomic元素（比如int/boolean/symbol，注意这里不是最小的表达式），直接解析运算，并写好用例

表达式处理

对于表达式（比如某种括号/数字开头），需要扫描两次

切分表达式

第一遍扫描（delimeter）：此处对括号split，不含嵌套（遇到多个括号嵌套时，不处理，直接append进去）。举个例子，比如计算器

(+ (* 2 (+ 6 7)) (* 4 5))

我将解析为如下，注意保留了括号，这里本质上是一个退化的链表

['+', '* 2 3 (+ 6 7)', '* 4 5']

而不是AST的树形结构

['+', ['*', '2', '3', ['+', '6', '7']], ['*','4', '5']]

如果你看过Clojure的实现，比如执行(let x 2 x)时，它将在Java侧通过LispReader解析为List表达式，后续步骤将在Clojure的Runtime进行invoke，而不是把工作全部扔到了Reader中，这样做当然是最工程化的；而如果你是在做题时，如果通过嵌套List，那么类型强制转换、Symbol状态保存、env与String的编码将比较繁琐，因此我个人建议通过保留括号String而不是维护嵌套List

执行表达式

第二遍扫描（eval）：通过匹配startWith（使用下面的readInt与readLetter等工具实现，没有转为单独的Tree，没有达到Parser的级别）实现DFA，并根据表达式进行eval（递归/Stack ，复杂度为N!）

这里扫描两次并不会太慢，因为如果只扫描一遍就全部搞定的话，需要维护很多全局变量与If判断（而且很难总结为经验），即通过很多goto语句实现DFA与AST，也就是所谓的意大利面式代码，导致调试中的index位置非常复杂。同时，由于你经常通过两次扫描进行训练，可以更专注在核心eval上，而不是反复折腾全局变量，真正白板时，对bugfree要求还是很高的。

例子

我们挑一个中等的题目，要求如下

https://leetcode.com/problems/number-of-atoms/

解决方法就是构造DFA遍历执行

附录

表达式到底扫描几遍

王垠曾经说过，在TOKEN扫描的时候不要为了节约遍历而做Parse/eval的工作，否则额外的判断与全局变量等问题会提高复杂度，我个人也赞成垠神的说法，因为这类问题一般不会有性能问题，N与2N不会太大。

此外，如果是为了做题/最小复杂度，那么尽可能不形成AST，而是直接保存split后的String，因为时间可能不够。

// array x is to fix immutable primary type
// x 的管理也由上游控制
int readDigit(String s, int i, int[] x){
    int n = s.charAt(i) - '0';
    while(i + 1 < s.length() && Character.isDigit(s.charAt(i+1))){
       n = n*10 + s.charAt(i+1) - '0';
       i++;
    }
  	x[0] = n;
    return i;
}

// StringBuilder是为了方便上游滑动窗口等复用， sb的释放由上游负责
public int readLetter(String s, int i, StringBuilder sb){
    sb.append(s.charAt(i));
    while(i+1 < s.length() && Character.isLetter(s.charAt(i+1)) ){
        sb.append(s.charAt(i+1));
        i++;
    }
    return i;
}

// usage，非常优雅，没有任何if是多余的
for(int i = 0;i<s.length();i++){
  char c = s.charAt(i);
  if(Character.isDigit(c)){
    int[] num = new int[1];
    i = readDigit(s, i, num);
  } else if(Character.isLetter(c)){
    i = readLetter(s, i, sb);
  }
}

除了手写，还有正则表达式匹配，但是感觉失去了本质