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