parsing - How does a simple calculator with parentheses work?

Question

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

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 (rather than 3 x 10 - 2 = 28)

And then consider this:

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?

Answer 1

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

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+

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.

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

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