シラバス レッスン 250 中 209 · プロジェクト:本物のものを作る
プロジェクト:本物のものを作る

プロジェクト:小さなインタープリター

これは通過儀礼です:言語を読んで実行するプログラムを書くのです。あなたの言語は算数ですが、本物のインタープリターと同じやり方で作るので、2 + 3 * 4 は 20 ではなく 14 になります。ここでは Python は助けてくれません - eval() なしで、文字列を自分で解析するのです。

2 つの段階があります。まずトークン化:生の文字列を部品のきれいなリストに変えます。"2 + 30" は ["2", "+", "30"] になります。文字をたどり、空白を飛ばし、+ - * / ( ) のそれぞれを独立したトークンとして出し、数字(と小数点)の連なりを 1 つの数のトークンに集めます。予期しない文字は ValueError です。

それから再帰下降を使って評価します:優先順位の段階ごとに 1 つの小さな関数があり、それぞれがその下の、より強く結び付くものを呼びます。その構造こそが、演算の順番を表しています:

def parse_expr():      # lowest precedence: + and -
    value = parse_term()
    while peek() in ("+", "-"):
        op = advance()
        value = value + parse_term() if op == "+" else value - parse_term()
    return value

def parse_term():      # higher: * and /
    value = parse_factor()
    while peek() in ("*", "/"):
        ...

def parse_factor():    # highest: a number, or ( expr )
    if peek() == "(":
        advance(); value = parse_expr()
        # then expect and consume the matching )
        ...
    return float(advance())

parse_factor はかっこで囲まれたまとまりのために parse_expr をもう一度呼べるので、かっこは入れ子のものも含めてただで手に入ります。peek()(今のトークンを見る)と advance()(それを消費する)を持つ小さな pos のカーソルを保ちましょう。形の崩れた入力では ValueError を送出しなければなりません:2 + のような宙ぶらりんの演算子、釣り合わない (2 + 3、あるいは残ったトークンです。狙う目標:evaluate('2 + 3 * 4') == 14.0、evaluate('(2 + 3) * 4') == 20.0、入れ子のかっこ、そして '2 +' でのエラーです。実行を押して、いくつかの式を評価しましょう。

あなたの番

tokenize(expr)(数は文字列のトークンとして、それに記号 + - * / ( )、空白は飛ばし、未知の文字は拒否する)と、+ - より * / を優先し、かっこを尊重する(再帰下降か操車場アルゴリズム)float を返す evaluate(expr) を書いてください。形の崩れた入力では ValueError を送出しなければなりません。目標:evaluate('2 + 3 * 4') == 14.0、evaluate('(2 + 3) * 4') == 20.0、入れ子のかっこ、そして '2 +' でのエラーです。

このレッスンに問題を見つけましたか?報告する · このレッスンについて質問する

この演習はまもなく開きます

その前のレッスンを終えると、このレッスンが解放されます。コース全体が無料でアカウントも不要、このレッスンは今すぐ読めます。