逆ポーランド記法（後置記法）を見ると、演算子の位置が変わっているため「どこが区切りなのかわからず、元の数式には戻せないのでは」と感じることがあります。しかし、逆ポーランド記法は決められたルールで変換されるため、情報が失われているわけではありません。この記事では、逆ポーランド記法から元の数式を復元できる理由と、その具体的な方法について解説します。
逆ポーランド記法とは何か
逆ポーランド記法とは、演算子を計算対象の後ろに置く表記方法です。通常の数式では演算子が数字の間に入りますが、逆ポーランド記法では数字を先に並べ、その後に演算子を置きます。
例えば、通常の中置記法である「a+b」は、逆ポーランド記法では「ab+」になります。これは「aとbを取り出して足し算する」という意味になります。
この形式では括弧が不要になるため、コンピューターが数式を処理するときに便利です。特にスタックというデータ構造と相性がよく、計算機やコンパイラなどで利用されています。
区切りがなくても逆ポーランド記法を復元できる理由
一見すると「abc*d-+」のような文字列では、どこからどこまでが一つの式なのかわからないように見えます。しかし、逆ポーランド記法では演算子を見ることで構造を一意に決めることができます。
重要なのは、演算子には必ず必要な項数が決まっているという点です。例えば「+」「-」「*」「/」はすべて2つの値を必要とする二項演算子です。
そのため、右側から処理するのではなく、左から順番に読んでいき、演算子が出てきた時点で直前の2つの要素を組み合わせれば、元の構造を再現できます。
具体例で逆ポーランド記法を元に戻す方法
例えば「ab+c-d*」という逆ポーランド記法を考えます。この式を左から読みます。
aとbは数値（または変数）なので、そのまま保存します。次に「+」が出てくるため、aとbを使って「(a+b)」になります。
続いてcを読み込み、「-」が出た時点で「(a+b)-c」となります。さらにdを読み込み、「*」が出るため、「((a+b)-c)*d」という形に復元できます。
質問の例「abc*d-+」を復元するとどうなるか
「abc*d-+」をスタックを使って復元してみます。
まずa、b、cを順番に保存します。次に「*」が出るので、直前のbとcを組み合わせて「(b*c)」になります。
次にdを読み込み、「-」が出るため「(b*c)-d」になります。最後に「+」が出るので、aと「(b*c-d)」を組み合わせ、「a+((b*c)-d)」になります。
つまり、この逆ポーランド記法は「a+b」など単純な足し算ではなく、演算子の位置によって元の構造が決定されています。括弧が書かれていなくても、演算子の数と順番から一意に判断できます。
逆ポーランド記法で区切りが不要になる仕組み
通常の数式では「a+b*c」のように演算子の優先順位を考える必要があります。また、「(a+b)*c」のように括弧で計算順序を指定する場合もあります。
一方、逆ポーランド記法では演算子の場所そのものが計算順序を表しています。そのため、括弧や優先順位のルールを別途考える必要がありません。
また、実際のプログラムでは数字や変数を1文字として扱うとは限らないため、「123」や「value」のような複数文字の要素を使う場合は、スペースや区切り記号を入れて表現します。
逆ポーランド記法を復元するときのポイント
逆ポーランド記法を中置記法へ戻す場合は、スタックを使う方法が一般的です。
手順は単純で、値が来たらスタックに入れ、演算子が来たらスタックから必要な数だけ値を取り出して新しい式を作り、再びスタックへ戻します。
この処理を最後まで繰り返すと、最終的に元の数式全体が完成します。コンピューターが逆ポーランド記法を扱いやすい理由も、この規則性にあります。
まとめ｜逆ポーランド記法は区切りがなくても復元可能
逆ポーランド記法は、見た目では区切りがわかりにくくても、演算子の位置と必要な項数によって数式の構造が完全に決まっています。
そのため「abc*d-+」のような表記でも、スタックを利用すれば元の数式へ正確に戻すことができます。
逆ポーランド記法は情報を省略しているのではなく、計算順序を別の形で表現している記法であり、コンピューターにとって扱いやすい効率的な表現方法なのです。
コメント