かっこ付きの簡単な計算機はどのように機能しますか？

Question

計算機の仕組みを学びたい。 2

パーサ数学に共通のルールを尊重しなければならない -

1 + 2×10は、たとえば、我々はこのようなインフィックス表記で入力を持っていると言います。 2 = 19（というより3×10 - - 2 = 28）

をし、この検討

1 +（2×10）：

1 + 2×上記の例では、この手段（（2/9）+ 7） - 2

抽象構文木は関係していますか？バイナリツリー？演算の順序はどのように数学的に正しいことが保証されていますか？これを後置記号に変換するためにシャントヤードアルゴリズムを使用する必要がありますか？そして、後置記法でどのように解析すればよいでしょうか？なぜ最初に変換するのですか？

これらの比較的単純な電卓がどのように構築されているかを示すチュートリアルはありますか？または誰かが説明することができますか？

Answer 1

式を評価する1つの方法は、再帰的降下パーサを使用することです。 http://en.wikipedia.org/wiki/Recursive_descent_parser

ここBNFの形態での文法は次のとおりここ http://en.wikipedia.org/wiki/Backus-Naur_form

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

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

Number ::= Digit+ 

*は、1つ以上の反復を意味+、先行する要素が0回以上繰り返される手段、角括弧はオプションを意味します。

文法は、最も高い優先度の要素が最初に一緒に集められるか、この場合は最初に評価されることを保証します。 文法の各ノードにアクセスするときに、抽象構文ツリーを構築するのではなく、現在のノードを評価して値を返します。

例コード（完璧ではないが、あなたのコードにBNFをマッピングする方法のアイデアを与える必要があります）：

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 

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 

Answer 2

を探して試してみてくださいAntlr。これは、私がカスタムコンパイラ/パーサを構築するために使用したものです...そして、作成するのは非常に簡単なことになる電卓と簡単に関連しています。