parsing - usar - ¿Cómo funciona una calculadora simple con paréntesis?

operaciones con calculadora cientifica

Question

Quiero aprender cómo funcionan las calculadoras. Por ejemplo, digamos que tenemos entradas en notación de infijo como esta:

1 + 2 x 10 - 2

El analizador tendría que respetar reglas comunes en matemáticas. En el ejemplo anterior esto significa:

1 + (2 x 10) - 2 = 19 (en lugar de 3 x 10 - 2 = 28)

Y luego considera esto:

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

¿Implica un árbol de sintaxis abstracta? Un árbol binario? ¿Cómo se garantiza que el orden de las operaciones sea matemáticamente correcto? ¿Debo usar el algoritmo de derivación para convertir esto a notación postfix? Y luego, ¿cómo lo analizaría en notación postfix? ¿Por qué convertir en primer lugar?

¿Existe un tutorial que muestre cómo se construyen estas calculadoras relativamente simples? ¿O alguien puede explicar?

Answer 1

Intenta mirar a Antlr . Es lo que usé para construir un compilador / analizador personalizado ... y podría relacionarme fácilmente con una calculadora que sería algo muy simple de crear.

Answer 2

Una forma de evaluar una expresión es con un analizador de descenso recursivo. http://en.wikipedia.org/wiki/Recursive_descent_parser

Aquí hay un ejemplo de gramática en formato BNF: http://en.wikipedia.org/wiki/Backus-Naur_form

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

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

Number ::= Digit+

Aquí * significa que el elemento anterior se repite cero o más veces, + significa una o más repeticiones, corchetes significa opcional.

La gramática garantiza que los elementos de mayor prioridad se recopilen primero, o en este caso, se evalúen primero. A medida que visita cada nodo en la gramática, en lugar de crear un árbol de sintaxis abstracta, evalúa el nodo actual y devuelve el valor.

Código de ejemplo (no es perfecto, pero debería darle una idea de cómo asignar BNF a código):

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

Para mostrar cómo se evaluaría su ejemplo de 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