Codewars:从逆波兰表达式到Three-Pass编译器(2)

在这里我想说的第二道题,我把它理解成一次对逆波兰表达式的运用和延伸。关于逆波兰表达式的相关知识,可以在前一篇博客中读到 : Codewars:从逆波兰表达式到Three-Pass编译器(1) 和前一题相比,这道题的题面就要复杂多了。 我们有一种如下的语法规则的编程语言: [ a b ] a*a + b*b 这里我们定义了一个函数,这个函数有两个参数(a 和 b),函数功能是计算 a 和 b 的平方和。 现在,请为该语言实现一个简单的语法编译器。编译过程可以拆分为三个步骤: 1.将函数解析为一个抽象语法树(AST ) AST有如下规则: { 'op': '+', 'a': a, 'b': b } // add subtree a to subtree b { 'op': '-', 'a': a,…

Codewars:从逆波兰表达式到Three-Pass编译器(1)

最近沉迷于在 codewars 上做题无法自拔,其中有两道题我感觉挺有意思,觉得值得记下来,故成此文。 第一道题的题面非常简单,实现一个包含 + - * / 四则运算的计算器,输入样例:1 + 2 * 3, 期望结果 7。 原题链接见下: https://www.codewars.com/kata/calculator 从小学数学的角度来思考这道题,答案是显而易见的:乘除法的优先级要高于加减法,所以我们可以把表达式中所有乘除法先提出来计算出结果并放回原来的位置,再依次计算加减法得到整个表达式的结果。依照这样的思路,我们可以有如下的代码实现(In Python): from operator import add, sub, mul, div FIRST = {'*' : mul, '/': div} SECOND = {'+': add,…