プログラミング
 Computer >> コンピューター >  >> プログラミング >> プログラミング

データ構造入門：前置記法（プレフィックス）と後置記法（ポストフィックス）の基礎

算術式を書き表す方法は「記法（ノーテーション）」と呼ばれます。算術式は、式の本質や計算結果を変えることなく、3つの異なる記法で表現できます。その3つが以下の通りです。

  • 中置記法（Infix）
  • 前置記法（Prefix）
  • 後置記法（Postfix）

中置記法は、私たちが日常的に数式を書く際に使う標準的な記法です。一方、前置記法と後置記法はこれとは大きく異なる特徴を持っています。

前置記法（Prefix Notation）とは

前置記法では、演算子を被演算子（オペランド）の前に置くのが特徴です。つまり、演算子がオペランドより先に書かれます。例えば +ab は、中置記法の a + b と同じ意味になります。前置記法は「ポーランド記法（Polish Notation）」とも呼ばれています。

後置記法（Postfix Notation）とは

後置記法は「逆ポーランド記法（Reversed Polish Notation）」として知られる記法です。この記法では、演算子を被演算子の後に置きます。例えば ab+ は、中置記法の a + b に相当します。

記法の変換例

No.中置記法前置記法後置記法
1a + b+ a ba b +
2(a + b) * c* + a b ca b + c *
3a * (b + c)* a + b ca b c + *
4a / b + c / d+ / a b / c da b / c d / +
5(a + b) * (c + d)* + a b + c da b + c d + *
6((a + b) * c) - d- * + a b c da b + c * d -

なぜ式の解析に前置・後置記法を使うのか

前述のとおり、中置記法のままアルゴリズムやプログラムで式を解析するのは効率的とは言えません。そこで実際には、中置記法の式をまず後置記法または前置記法に変換してから計算処理を行います。

また、算術式を正しく解析するためには、「演算子の優先順位」と「結合規則」にも注意を払う必要があります。

演算子の優先順位

1つのオペランドが2種類の演算子の間に挟まれている場合、どちらの演算子が先にそのオペランドを扱うかは、演算子同士の優先順位によって決まります。例を見てみましょう。

a + b * c → a + (b * c)

乗算（掛け算）は加算（足し算）よりも優先順位が高いため、b * c が先に評価されます。演算子ごとの優先順位の一覧表については、後ほど詳しく紹介します。

  1. ハーフエッジデータ構造（HalfedgeDS）とは？基本概念とCGAL実装例をわかりやすく解説

    はじめにテンプレートパラメータとして用いられるハーフエッジデータ構造（Halfedge Data Structure、略称 HalfedgeDS）は、頂点・辺・面の接続情報（インシデンス情報）を管理できる、辺を中心としたデータ構造として定義されています。平面地図（planar map）や多面体など、任意の次元空間に埋め込まれた向き付け可能な2次元曲面の表現に適した構造です。このデータ構造では、各辺が逆向きの向きを持つ2つのハーフエッジ（半辺）に分割されます。各ハーフエッジは、隣接する1つの面と1つの頂点への参照を保持し、逆に各面および各頂点にも、それぞれ1つの接続ハーフエッジが格納されます。さ

  2. 【データ構造】適応型マージソート（Adaptive Merge Sort）の仕組みと計算量を徹底解説

    適応型マージソート（Adaptive Merge Sort）とは適応型マージソートは、通常のマージソートと同様にソート済みの部分リストをマージ（併合）していくソートアルゴリズムです。ただし、従来のマージソートが要素数1の部分リストから処理を開始するのに対し、適応型マージソートでは、リスト内にすでに存在する「整列済みの並び」を検出し、そのまとまりをそのまま初期の部分リストとして利用します。これにより、順序が整った要素を無駄に分割・再マージすることなく、マージの回数を大幅に削減できます。例として、次の図のようなリストを考えてみましょう。このリストは、あらかじめ2つのソート済み部分リストで構成されて