JavaScriptのスタックを使った逆ポーランド記法（RPN）計算機の実装方法

逆ポーランド記法（RPN）計算機とは

JavaScriptのスタック（Stack）データ構造を活用して、RPN（Reverse Polish Notation：逆ポーランド記法）入力方式の計算機を作成する方法を解説します。逆ポーランド記法は演算子を被演算子の後ろに置く記法で、括弧が不要になり、スタックを使った実装と非常に相性が良いのが特徴です。

入力配列の例

まず、次のような入力配列を考えてみましょう。

const arr = [1, 5, '+', 6, 3, '-', '/', 7, '*'];

処理の流れ

• 1 はオペランド（被演算子）なので、スタックにプッシュします。
• 5 はオペランドなので、スタックにプッシュします。
• '+' は演算子なので、スタックから 1 と 5 をポップして加算し、結果をスタックにプッシュします。
• 6 はオペランドなので、スタックにプッシュします。
• 3 はオペランドなので、スタックにプッシュします。
• '-' は演算子なので、スタックから 6 と 3 をポップして減算し、結果をスタックにプッシュします。
• '/' は演算子なので、スタックから 6 と 3 をポップして除算し、結果をスタックにプッシュします。
• 7 はオペランドなので、スタックにプッシュします。
• '*' は演算子なので、スタックから 2 と 7 をポップして乗算し、結果をスタックにプッシュします。

最終的にスタックに残る値、つまり出力結果は以下のとおりです。

const output = 14;

実装コード例

この計算機は次のように実装できます。

const arr = [1, 5, '+', 6, 3, '-', '/', 7, '*'];
const stackCalculator = (arr = []) => {
  const options = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => a / b
  };
  const stack = [];
  arr.forEach(value => {
    stack.push(value in options
      ? options[value](...stack.splice(-2))
      : value
    );
  });
  return stack;
};
console.log(stackCalculator(arr));

コードのポイント

この実装の鍵となるのは stack.splice(-2) の部分です。配列の末尾から2つの要素（最後にプッシュされた2つのオペランド）を取り出し、それらを演算子に対応する関数へ渡しています。演算子ごとの処理はオブジェクト options にまとめられているため、%（剰余）や **（べき乗）など、新しい演算子の追加も簡単に行えます。

実行結果

コンソールには以下のように出力されます。

[14]