Come funziona una semplice calcolatrice con parentesi?

Question

Voglio imparare come funzionano i calcolatori. Ad esempio, dire che abbiamo ingressi in notazione infissa in questo modo:

1 + 2 x 10 - 2

Il parser avrebbe dovuto rispettare le regole comuni in matematica. Nell'esempio sopra significa:

1 + (2 x 10) - 2 = 19 (anziché 3 x 10 - 2 = 28)

E poi considerare questo:

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

Comprende un Abstract Syntax Tree? Un albero binario? In che modo l'ordine delle operazioni è assicurato per essere matematicamente corretto? Devo usare l'algoritmo dello shunting-yard per convertire questo in notazione postfissa? E poi, come potrei analizzarlo nella notazione postfix? Perché convertire in primo luogo?

Esiste un tutorial che mostra come vengono costruiti questi calcolatori relativamente semplici? O qualcuno può spiegare?

Answer 1

Un modo per valutare un'espressione è con un parser di discesa ricorsivo. http://en.wikipedia.org/wiki/Recursive_descent_parser

Ecco un esempio di grammatica in forma BNF: http://en.wikipedia.org/wiki/Backus-Naur_form

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

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

Number ::= Digit+ 

Qui * significa che l'elemento precedente viene ripetuto zero o più volte, + significa una o più ripetizioni, tra parentesi quadre significa opzionale.

La grammatica garantisce che gli elementi di precedenza più alta vengano raccolti prima o, in questo caso, prima valutati. Mentre si visita ciascun nodo nella grammatica, anziché creare un albero di sintassi astratto, si valuta il nodo corrente e si restituisce il valore.

codice di esempio (non perfetto, ma dovrebbe darvi un'idea di come mappare BNF a codice):

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 

per mostrare come il tuo esempio di 1 + 2 * 10 - 2 valuterà:

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

Prova a guardare a Antlr. È quello che ho usato per costruire un compilatore/parser personalizzato ... e che potrebbe facilmente riguardare un calcolatore che sarebbe una cosa molto semplice da creare.