我想了解计算器的工作原理。例如,假设我们有这样的中缀表示法输入:
1 + 2 x 10 - 2
解析器必须遵守数学中的常见规则。在上面的示例中,这意味着:
1 + (2 x 10) - 2 = 19(而不是 3 x 10 - 2 = 28)
然后考虑一下:
1 + 2 x ((2/9) + 7) - 2
它涉及抽象语法树吗?二叉树?如何确保运算顺序在数学上正确?我必须使用调车场算法将其转换为后缀表示法吗?然后,我如何用后缀表示法解析它?为什么首先要进行转换?
是否有教程展示这些相对简单的计算器是如何构建的?或者谁能解释一下?
最佳答案
计算表达式的一种方法是使用递归下降解析器。 http://en.wikipedia.org/wiki/Recursive_descent_parser
下面是 BNF 形式的语法示例: http://en.wikipedia.org/wiki/Backus-Naur_form
Expr ::= Term ('+' Term | '-' Term)*
Term ::= Factor ('*' Factor | '/' Factor)*
Factor ::= ['-'] (Number | '(' Expr ')')
Number ::= Digit+
这里*表示前面的元素重复零次或多次,+表示重复一次或多次,方括号表示可选。
语法确保首先将最高优先级的元素收集在一起,或者在本例中,首先评估。 当您访问语法中的每个节点时,您不是构建抽象语法树,而是评估当前节点并返回值。
示例代码(并不完美,但应该让您了解如何将 BNF 映射到代码):
def parse_expr():
term = parse_term()
while 1:
if match('+'):
term = term + parse_term()
elif match('-'):
term = term - parse_term()
else: return term
def parse_term():
factor = parse_factor()
while 1:
if match('*'):
factor = factor * parse_factor()
elif match('/'):
factor = factor / parse_factor()
else: return factor
def parse_factor():
if match('-'):
negate = -1
else: negate = 1
if peek_digit():
return negate * parse_number()
if match('('):
expr = parse_expr()
if not match(')'): error...
return negate * expr
error...
def parse_number():
num = 0
while peek_digit():
num = num * 10 + read_digit()
return num
要展示 1 + 2 * 10 - 2
示例的计算结果:
call parse_expr stream is 1 + 2 * 10 - 2
call parse term
call parse factor
call parse number which returns 1 stream is now + 2 * 10 - 2
match '+' stream is now 2 * 10 - 2
call parse factor
call parse number which returns 2 stream is now * 10 - 2
match '*' stream is now 10 - 2
call parse number which returns 10 stream is now - 2
computes 2 * 10, return 20
compute 1 + 20 -> 21
match '-' stream is now 2
call parse factor
call parse number which returns 2 stream is empty
compute 21 - 2, return 19
return 19
关于parsing - 带括号的简单计算器如何工作?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9785553/