괄호가있는 간단한 계산기는 어떻게 작동합니까?

Question

저는 계산기가 어떻게 작동하는지 배우고 싶습니다. 2

파서 수학의 일반적인 규칙을 존중해야 -

1 + 2 × (10)는 예를 들어, 우리는 다음과 같이 중위 표기법에 입력을 말한다. 2 = 19 (보다 3 X 10 - - 2 = 28)

하고 다음이 고려

1 + (2 ×) :

1 + 2 (X) 상기의 예에서, 이는 ((2/9) + 7) - 2

추상 구문 트리가 관련되어 있습니까? 이진 트리? 연산 순서가 수학적으로 어떻게 정확합니까? 이것을 뒷좌석 표기법으로 변환하려면 shunting-yard 알고리즘을 사용해야합니까? 그리고 나서 어떻게 후치 표기법으로 파싱 할 것인가? 왜 처음부터 개종 했습니까?

이 비교적 간단한 계산기가 어떻게 구성되어 있는지 보여주는 자습서가 있습니까? 또는 누군가 설명 할 수 있습니까?

Answer 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+ 

는 * 괄호는 선택 수단 선행 요소 + 하나 이상의 반복을 의미하고, 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에 있습니다. 그것은 내가 커스텀 컴파일러/파서 (parser)를 만드는 데 사용했던 것입니다 ... 그리고 아주 간단하게 작성할 수있는 계산기와 쉽게 관련 될 수 있습니다.