带括号的简单计算器如何工作? [英] How does a simple calculator with parentheses work?

问题描述

我想了解计算器的工作原理.例如，假设我们有这样的中缀符号输入:

I want to learn how calculators work. For example, say we have inputs in infix notation like this:

1 + 2 x 10 - 2

1 + 2 x 10 - 2

解析器必须遵守数学中的通用规则.在上面的例子中，这意味着:

The parser would have to respect common rules in math. In the above example this means:

1 + (2 x 10) - 2 = 19(而不是 3 x 10 - 2 = 28)

1 + (2 x 10) - 2 = 19 (rather than 3 x 10 - 2 = 28)

然后考虑这个:

1 + 2 x ((2/9) + 7) - 2

1 + 2 x ((2 / 9) + 7) - 2

它是否涉及抽象语法树?二叉树?如何确保运算顺序在数学上是正确的?我必须使用调车码算法将其转换为后缀表示法吗?然后，我将如何用后缀表示法解析它?为什么首先要转换?

Does it involve an Abstract Syntax Tree? A binary tree? How is the order of operations ensured to be mathematically correct? Must I use the shunting-yard algorithm to convert this to postfix notation? And then, how would I parse it in postfix notation? Why convert in the first place?

是否有教程展示了这些相对简单的计算器是如何构建的?或者有人可以解释一下吗?

Is there a tutorial which shows how these relatively simple calculators are built? Or can someone explain?

推荐答案

对表达式求值的一种方法是使用递归下降解析器.http://en.wikipedia.org/wiki/Recursive_descent_parser

One way to do evaluate an expression is with a recursive descent parser. http://en.wikipedia.org/wiki/Recursive_descent_parser

这是一个 BNF 形式的语法示例:http://en.wikipedia.org/wiki/Backus-Naur_form

Here's an example grammar in BNF form: http://en.wikipedia.org/wiki/Backus-Naur_form

Expr ::= Term ('+' Term | '-' Term)*
Term ::= Factor ('*' Factor | '/' Factor)*

Factor ::= ['-'] (Number | '(' Expr ')')

Number ::= Digit+

这里*表示前面的元素重复0次或多次，+表示重复一次或多次，方括号表示可选.

Here * means the preceding element is repeated zero or more times, + means one or more repeats, square brackets means optional.

语法确保最高优先级的元素首先收集在一起，或者在这种情况下，首先评估.当您访问语法中的每个节点时，您不是构建抽象语法树，而是评估当前节点并返回值.

The grammar ensures that the elements of highest precedence are collected together first, or in this case, evaluated first. As you visit each node in the grammar, instead of building an abstract syntax tree, you evaluate the current node and return the value.

示例代码(不完美，但应该让您了解如何将 BNF 映射到代码):

Example code (not perfect but should give you an idea of how to map BNF to code):

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 示例将如何评估:

To show how your example of 1 + 2 * 10 - 2 would evaluate:

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

这篇关于带括号的简单计算器如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！