Geekly Articles each Day

Pythonで50行の数式を解析する

インスピレーション-Yandexと記事「40行の数式を解析する」 にインタビューするタスク 。

私の目標は、この問題に対するpythonicソリューションがどのようになるかを確認することでした。 ソリューションがシンプルで、コードが読み取り可能で共有されていることを望みました。 その結果、ジェネレーターのチェーン（ジェネレーターパイプライン）の使用例も得られました。

Yandexは、その記事-Sorting Station Algorithmで問題を解決するための古典的なアルゴリズムを指摘しました。

このアルゴリズムは、使い慣れた中置表記の式を逆ポーランド語に変換します。
逆ポーランド記法（OPN）での式の計算は、単純なアルゴリズムを備えているため魅力的です。

式計算アルゴリズム全体は、次の3つの部分に分かれています。

  1. 数値と演算子の元の文字列を解析する
  2. アレスタ内の式を取得するための選別ステーションアルゴリズムの適用
  3. アレスタでの式計算

ステージ1および2の出力で、数値と演算子の配列を取得します。 ジェネレーターのチェーンとして機能を実装する大きな誘惑。 式は数値と演算子が到着すると計算される遅延データ処理を使用して、メモリ消費を削減します。

それでは始めましょう


まず、演算子を辞書形式で定義します。各シンボルについて、優先度と計算関数を決定します。
この辞書は、シンボルが演算子であるかどうかを判断するのにも役立ちます。

OPERATORS = {'+': (1, lambda x, y: x + y), '-': (1, lambda x, y: x - y), '*': (2, lambda x, y: x * y), '/': (2, lambda x, y: x / y)}

関数eval_定義します。その入力は、計算式を含む文字列です。

 def eval_(formula_string):

関数内で、関数と2つのジェネレーターを定義します。それぞれがその役割を果たします。

1.ソース行パーサー

ジェネレーターは入力文字列を受け取り、フロート形式の数値、文字形式の演算子とブラケットを返します。

  def parse(formula_string): number = '' for s in formula_string: if s in '1234567890.': #   - ,    number += s elif number: #    ,         yield float(number) number = '' if s in OPERATORS or s in "()": #   -   ,     yield s if number: #      ,   yield float(number)

2.選別ステーションのアルゴリズム

ジェネレータは、入力として中置表記法で数値と演算子の反復可能なオブジェクトを受け取り、逆ポーランド表記法で数値と演算子を返します。

  def shunting_yard(parsed_formula): stack = [] #      for token in parsed_formula: #   - ,       , #      , #      . #    ,    - if token in OPERATORS: while stack and stack[-1] != "(" and OPERATORS[token][0] <= OPERATORS[stack[-1]][0]: yield stack.pop() stack.append(token) elif token == ")": #   -  ,     ,   , #      . while stack: x = stack.pop() if x == "(": break yield x elif token == "(": #   -  ,      stack.append(token) else: #   - ,      yield token while stack: yield stack.pop()

3.電卓

この関数は、数値と演算子の反復可能なオブジェクトを逆ポーランド表記法で受け取り、計算の結果を返します。

  def calc(polish): stack = [] for token in polish: if token in OPERATORS: #    - , y, x = stack.pop(), stack.pop() #  2    stack.append(OPERATORS[token][1](x, y)) #  ,    else: stack.append(token) return stack[0] #   -

最後に、関数eval_の結果を計算するジェネレーターのチェーンを構成します。

  return calc(shunting_yard(parse(formula_string)))

性能


最も重要な質問：「プログラムはどのくらい速く動作しますか？」関数と組み込み関数evalを比較してください。

単純な場合、関数はさらに高速です！

 %timeit eval("2+2") 100000 loops, best of 3: 12.8 µs per loop %timeit eval_("2+2") 100000 loops, best of 3: 7.61 µs per loop

より複雑な式-22％長い：

 %timeit eval("15/(7-(1+1))*3-(2+(1+1))") 10000 loops, best of 3: 29.7 µs per loop %timeit eval_("15/(7-(1+1))*3-(2+(1+1))") 10000 loops, best of 3: 36.3 µs per loop

式ではさらに複雑になります-ギャップは広がりますが、関数の速度はビルトインに匹敵します：

 %timeit eval("15/(7-(1+1))*3-(2+(1+1))*15/(7-(1+1))*3-(2+(1+1))*(15/(7-(1+1))*3-(2+(1+1))+15/(7-(1+1))*3-(2+(1+1)))") 10000 loops, best of 3: 86.3 µs per loop %timeit eval_("15/(7-(1+1))*3-(2+(1+1))*15/(7-(1+1))*3-(2+(1+1))*(15/(7-(1+1))*3-(2+(1+1))+15/(7-(1+1))*3-(2+(1+1)))") 10000 loops, best of 3: 147 µs per loop

はい、記事のタイトルを思い出してください。読みやすさとPEP8を忘れずに、50行しかありません。

機能コード全体
 OPERATORS = {'+': (1, lambda x, y: x + y), '-': (1, lambda x, y: x - y), '*': (2, lambda x, y: x * y), '/': (2, lambda x, y: x / y)} def eval_(formula): def parse(formula_string): number = '' for s in formula_string: if s in '1234567890.': number += s elif number: yield float(number) number = '' if s in OPERATORS or s in "()": yield s if number: yield float(number) def shunting_yard(parsed_formula): stack = [] for token in parsed_formula: if token in OPERATORS: while stack and stack[-1] != "(" and OPERATORS[token][0] <= OPERATORS[stack[-1]][0]: yield stack.pop() stack.append(token) elif token == ")": while stack: x = stack.pop() if x == "(": break yield x elif token == "(": stack.append(token) else: yield token while stack: yield stack.pop() def calc(polish): stack = [] for token in polish: if token in OPERATORS: y, x = stack.pop(), stack.pop() stack.append(OPERATORS[token][1](x, y)) else: stack.append(token) return stack[0] return calc(shunting_yard(parse(formula)))

Source: https://habr.com/ru/post/J273253/

More articles:


All Articles