波兰表达式

为了验证 mpc 的威力，本章我们尝试实现一个简单的语法解析器－－波兰表达式，它是我们将要实现的 Lisp 的数学运算部分。波兰表达式也是一种数学标记语言，它的运算符在操作数的前面。

举例来说：

普通表达式 波兰表达式
1 + 2 + 6 + 1 2 6
6 + (2 * 9) + 6 (* 2 9)
(10 * 2) / (4 + 2) / (* 10 2) (+ 4 2)

现在，我们需要编写这种标记语言的语法规则。我们可以先用白话文来尝试描述它，而后再将其公式化。

我们观察到，波兰表达式总是以操作符开头，后面跟着操作数或其他的包裹在圆括号中的表达式。也就是说，“程序(Program)是由一个操作符(Operator)加上一个或多个表达式(Expression)组成的”，而 “表达式(Expression)可以是一个数字，或者是包裹在圆括号中的一个操作符(Operator)加上一个或多个表达式(Expression)”。

下面是一个更加规整的描述：

名称 定义
程序(Program) 开始输入 —> 操作符 —> 一个或多个表达式(Expression) —> 结束输入
表达式(Expression) 数字、左括号 (、操作符 —> 一个或多个表达式 —> 右括号 )
操作符(Operator) '+'、'-'、'*' 、 '/'
数字(Number) 可选的负号 - —> 一个或多个 0 到 9 之间的字符