0503: 操作优先级

解析中缀表达式的难点就是处理运算优先级。编译原理有许多专门的方法，然而都不是必须的。实践上只要用简单的递归调用就能搞定。

多重优先级的包含关系

这一步增加乘除操作，优先级（precedence）比加减更高。暂时不考虑括号，一个同时包含加减乘除的表达式，加减必然是在树的上层（root）的。也就是说，加减操作的子树，可以包含乘除。而乘除操作的子树，不用括号的情况下不能包含加减，只能是一个值或者列名，也就是上一步的 parseAtom()。所以我们要做2个改动：

  1. 把 parseAdd() 复制一遍，稍微修改成 parseMul()，解析一个只包含乘除的表达式。
  2. 把 parseAdd() 中的 parseAtom() 换成 parseMul()，将乘除操作作为加减的子树。

解析一个有多重优先级的中缀表达式，从优先级最低的开始，优先级最高的在调用链最深处。现在增加 parseExpr() 函数，作为表达式解析的入口：

func (p *Parser) parseExpr() (interface{}, error) {
    return p.parseAdd()
}
func (p *Parser) parseAdd() (interface{}, error) {
    // 调用 parseMul()
}
func (p *Parser) parseMul() (interface{}, error) {
    // 调用 parseAtom()
}

这里只有2重优先级，要增加更多，依样画葫芦就行。

括号

现在增加括号，用来修改运算顺序。括号可以看做是优先级最高的操作，所以要在调用链最深的 parseAtom() 里处理。检测到括号后，调用最浅层的 parseExpr()。

func (p *Parser) parseAtom() (expr interface{}, err error) {
    if p.tryPunctuation("(") {
        if expr, err = p.parseExpr(); err != nil {
            return nil, err
        }
        if !p.tryPunctuation(")") {
            return nil, errors.New("expect )")
        }
        return expr, nil
    }
    // ...
}

您正在阅读免费版教程，从第4章起只有简单的指引，适合爱好挑战和自学的读者。
可以购买有详细指导+背景知识的完整版。