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, '-': sub}

class Calculator(object):
    def evaluate(self, string):
        tokens = [float(t) if t.isdigit() or '.' in t else t for t in string.split()]
        while True:
            for (i, token) in enumerate(tokens):
                op = FIRST.get(token)
                if op:
                    tokens[i - 1 : i + 2] = [op(tokens[i - 1], tokens[i + 1])]
                    break
            else:
                ret = tokens[0]
                for i in xrange(1, len(tokens), 2):
                    ret = SECOND[tokens[i]](ret, tokens[i + 1])
                return ret

或者,我们可以做得再优雅一点,先将表达式转化成一棵树:

    +
   /  \
  1    *
      / \
     2   3

然后再递归的从叶子开始求值,最后回到根,得出结果,这样,我们可以有如下实现:

from operator import sub, mul, add, div
from decimal import Decimal

OPFUN = {"+": add, "-": sub, "*": mul, "/": div}

class Calculator(object):
    def eval_list(self, parts):
        for oplist in [["+", "-"], ["*", "/"]]:
            for index in reversed(xrange(len(parts))):
                part = parts[index]
                if part in oplist:
                    return OPFUN[part](self.eval_list(parts[:index]), self.eval_list(parts[index+1:]))

        if len(parts) == 1:
            return Decimal(parts[0])

    def evaluate(self, string):
        return float(self.eval_list(string.split(" ")))

以上的实现方式都很棒,不过如果站在计算机的角度来思考这个问题,这样的实现方式显得有点不太自然。在第一种方式中,表达式的解析和运算是同时发生的,如果表达式很复杂,计算的速度会变慢;在第二种方式中,我们先将表达式转化成了一个树状结构,而对于一个比较复杂的表达式,树可能会很深,而且递归的过程将会消耗大量的内存,因此也不够理想。

是否存在这样一种可能,设计一种十分简单的表达形式,计算机只需要只要按顺序依次读入并按某种规则进行计算就可以得出计算结果?答案是肯定的,这就是逆波兰表达式。

来自维基百科:

逆波兰表示法(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

那么问题来了,我们要如何把一个普通的数学表达式(也叫中缀表达式)转换成逆波兰表达式的形式呢?维基百科上同样给出了答案,这就是 调度场算法

还是来自维基百科:

调度场算法(Shunting Yard Algorithm)是一个用于将中缀表达式转换为后缀表达式的经典算法,由艾兹格·迪杰斯特拉引入,因其操作类似于火车编组场而得名。

这里我们给出一个包括括号的中缀表达式例子,值得注意的是,在逆波兰表达式的写法中,我们不再需要通过加括号的方式来指定表达式计算的优先级。

调度场算法

那么,对于表达式 1+2*3 ,它的逆波兰表达式形式即为 123*+。不过知道怎么把我们熟悉的中缀表达式转换成逆波兰表达式仅仅是第一步,下面我们还需要知道如何对逆波兰表达式进行计算。那么,再看一个例子:

逆波兰表达式计算

现在,让我们再回到这道题,试试用逆波兰表达式的方式来得到答案。实现代码如下:

class Calculator(object):
  def evaluate(self, string):

      # 构造逆波兰表达式
      l = []
      operators = []
      for c in string.split(' '):
          if is_number(c):
              l.append(c)
          else:
              while len(operators) > 0:
                  if c in '*/' and operators[-1] in '+-':
                      break
                  else:
                      l.append(operators.pop())
              operators.append(c)
             
      # 计算逆波兰表达式
      stack = []
      for c in l + operators[::-1]:
          if is_number(c):
              stack.append(c)
          else:
              a = stack.pop()
              b = stack.pop()
              stack.append(str(eval(b + c + a))) 
      return float(stack.pop()) 
Show Comments