你熟悉正则表达式吗?如果没有,最好先了解它们。它们是解析的弱的、非递归的表亲。不要深入,只需了解构建块 - A 然后 B,A 很多次,A 或 B。
您找到的博客文章很难,因为它手动实现了解析。它使用递归下降,这是手动编写解析器并保持理智的唯一方法,但它仍然很棘手。
人们大部分时间所做的只是编写高级语法并使用库(或代码生成器)来完成解析的艰苦工作。事实上,他有一个较早的帖子,他使用了一个库:
http ://blog.erezsh.com/how-to-write-a-calculator-in-50-python-lines-without-eval/
至少开头应该是很容易。需要注意的事项:
优先级是如何从语法结构中产生的——add
由mul
s 组成,反之亦然。
他为括号添加规则的那一刻:
atom: neg | number | '(' add ')';
这就是它真正变得递归的地方!
6-2-1
应该解析为 (6-2)-1,而不是 6-(2-1)。他不讨论,但如果你仔细看,它也来自语法的结构。不要在这上面浪费时间;只是知道这称为关联性以供将来参考。
解析的结果是一棵树。然后,您可以以自下而上的方式计算其值。在“计算!” 章他这样做了,但是以一种神奇的方式。别担心。
自己做一个计算器,我建议你尽量去掉这个问题。
识别数字在哪里结束等有点混乱。它可以是语法的一部分,也可以由称为lexer或tokenizer的单独通道完成。
我建议你跳过它——要求用户在所有运算符和括号周围输入空格。或者只是假设您已经获得了一个表单列表[2.0, "*", "(", 3.0, "+", -1.0, ")"]
。
从一个仅处理 3 元素表达式的简单解析器(令牌)函数开始 - [number, op, number]。
返回一个数字,即计算的结果。(我之前说过解析器输出一个稍后处理的树。不用担心,返回一个数字更简单。)
编写一个需要数字或括号的函数——在后一种情况下,它调用 parser()。
>>> number_or_expr([1.0, "rest..."])
(1.0, ["rest..."])
>>> number_or_expr(["(", 2.0, "+", 2.0, ")", "rest..."])
(4.0, ["rest..."])
请注意,我现在返回第二个值 - 输入的剩余部分。更改 parser() 以也使用此约定。
现在重写 parser() 来调用 number_or_expr() 而不是直接假设 tokens[0] 和 tokens[2] 是数字。
中提琴!你现在有一个可以计算任何东西的(相互的)递归计算器——它只需要以冗长的风格编写,并在所有内容周围加上括号。
现在停下来欣赏你的代码,至少花一天时间 :-) 它仍然很简单,但具有解析的基本递归性质。并且代码结构反映了语法 1:1(这是递归下降的好特性。你不想知道其他算法的外观)。
从这里可以进行许多改进——支持 2+2+2、允许 (1)、优先级...——但有两种方法可以解决:
- 逐步改进您的代码。你将不得不重构很多。
- 停止努力并使用解析库,例如pyparsing。这将使您能够更快地尝试语法更改。