スタックと逆ポーランド記法

スタックは、最後に格納したデータを最初に取り出す後入れ先出し（LIFO: Last In First Out）の線形データ構造である。データの追加を挿入（push）、取出しを取出し（pop）と呼び、どちらも先頭の位置だけで行う。逆ポーランド記法（後置記法）は、演算子を被演算子の後ろに置く式の表記法であり、括弧と演算の優先順位を使わずに演算順序を一意に表せる。両者は、データの出力順序を求める問題と、式の評価を求める問題の双方で組み合わせて問われる。

スタックの基本動作と出力順序

スタックでは、常に先頭にあるデータだけが取り出せる。そのため、入力順に挿入したデータを途中で取り出すと、残りのデータは逆順に並んで出てくる性質がある。入力順が A, B, C であるデータを、各データについてスタックへの挿入と取出しを1回ずつ行う条件で処理すると、出力順序は5通りに限られる。

同じ条件を3個のデータに課した別の問題でも、出力順序は5通りとなる。この結果は、スタックでは全順列のうち一部の並びしか出力できないことを示している。

出力順序を数える際の注意

出力順序の数え方では、全順列の数と混同しないことが重要である。全順列は入力を任意の順に並べ替えられる場合の数であり、スタックでは挿入の順番が入力順に固定されるため、この制約を外すと数が過大になる。たとえば C, A, B の順で出すには、A, B, C の順にすべて挿入してから C を取り出す必要があり、次に取り出せるのは B に限られる。そのため、A を先頭にできず、CAB の出力は不可能である。

逆ポーランド記法の構造

中置記法では、A＋B×C のように演算子の位置と優先順位を考慮して演算順序を読み取る必要がある。後置記法では演算子が被演算子の後ろに置かれるため、演算順序は式の並びだけで決まる。A＋B×C は ABC×＋ と表され、B と C の積を先に求め、その結果に A を加えるという順序が左から右への読み取りで確定する。

一方、演算子が被演算子より前に現れる表記は、その演算に必要な二つの値がまだ揃っていないため評価できない。「×＋ABC」の先頭の×は、掛ける値が二つ存在しない時点で現れるので、式として成立しない。