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

Question

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

1 + 2 x 10 - 2

El analizador tendría que respetar normas 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 entonces considere esto:

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

¿Se trata de un árbol de sintaxis abstracto? Un árbol binario? ¿Cómo se asegura que el orden de las operaciones sea matemáticamente correcto? ¿Debo usar el algoritmo del patio de maniobras para convertir esto en notación de postfijo? Y luego, ¿cómo lo analizaría en la notación postfix? ¿Por qué convertir en primer lugar?

¿Hay algún tutorial que muestre cómo se crean estas calculadoras relativamente simples? ¿O alguien puede explicar?

Answer 1

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

Así es una gramática ejemplo en forma de 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 precedente se repite cero o más veces, + significa una o más repeticiones, corchetes medio opcional.

La gramática garantiza que los elementos de mayor precedencia se recopilan juntos primero o, en este caso, se evalúan primero. Al visitar cada nodo en la gramática, en lugar de crear un árbol de sintaxis abstracto, evalúa el nodo actual y devuelve el valor.

Ejemplo de código (no es perfecto, pero debe darle una idea de cómo asignar BNF de 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 el ejemplo de 1 + 2 * 10 - 2 evaluaría:

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 

Answer 2

Trate de buscar al Antlr. Es lo que solía construir un compilador/analizador personalizado ... y podría relacionarse fácilmente con una calculadora, lo que sería muy simple de crear.