Как работает простой калькулятор с круглыми скобками? - PullRequest
Новая
       21

Как работает простой калькулятор с круглыми скобками?

21 голосов
/ 20 марта 2012

Я хочу узнать, как работают калькуляторы.Например, скажем, у нас есть входные данные в инфиксной нотации, например:

1 + 2 x 10 - 2

Анализатор должен будет соблюдать общие правила математики.В приведенном выше примере это означает:

1 + (2 x 10) - 2 = 19 (а не 3 x 10 - 2 = 28)

И затем рассмотрим это:

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

Включает ли оно абстрактное синтаксическое дерево?Бинарное дерево?Как обеспечить математически правильный порядок операций?Должен ли я использовать алгоритм shunting-yard для преобразования этого в постфиксную нотацию?А потом, как бы я проанализировать его в постфиксной записи?Зачем конвертировать в первую очередь?

Есть ли учебник, который показывает, как создаются эти относительно простые калькуляторы?Или может кто-нибудь объяснить?

Ответы [ 2 ]

23 голосов
/ 20 марта 2012

Одним из способов оценки выражения является парсер рекурсивного спуска.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
3 голосов
/ 20 марта 2012

Попробуйте посмотреть Antlr . Это то, что я использовал для создания собственного компилятора / парсера ... и мог легко относиться к калькулятору, который было бы очень просто создать.

...