スタックで逆ポーランド記法の数式を計算する

前回の記事はこちら。

今回は前回から引き続きスタックの活用方法を見ていく。スタックの活用方法の例題としてよく挙げられるのが「逆ポーランド記法の数式を計算する」という課題である¹。ということで実際にJavascriptでスタックを使って上記の処理を実装してみる。

ここでは入力は「逆ポーランド記法で記述された半角スペース区切りの数字及び演算子の文字列1行」を想定する。なお以下のコードのStackは前回作成したものを使用する。

function solveRpn(input) {
  const inputs = input.split(' ');
  const s = new Stack();
  const numReg = /\d/;
  const opeReg = /\+|-|\*|\//;

  for (let val of inputs) {
    if (numReg.test(val)) {
      s.push(val);
    } else if (opeReg.test(val)) {
      const op2 = s.pop();
      const op1 = s.pop();
      s.push(eval(`${op1} ${val} ${op2}`));
    } else {
      console.error('Invalid arguments', val);
    }
  }
  return s.top === 1 ? s.pop() : NaN;
}
const val = solveRpn('1 2 + 5 2 - * 6 + 5 /'); // ((1+2) * (5-2) + 6) / 5 と等価
console.log('Answer', val); // 3

処理としては与えられた文字列の各文字をチェックし、数値であればスタックに追加、演算子(+, -, * , /)であれば直前の2つの要素を取り出して演算子を適用しスタックに追加している。数値と演算子のチェックは正規表現で行い、演算はevalで行っている。

eval内のバッククォートはES6で追加されたテンプレートリテラルというやつで、バッククォートのペア内で${hoge}のように変数名を書くとその内容を展開してくれるという便利機能である。

正確に計算できていれば最終的なスタックのサイズは1になっているはずなので、スタックのサイズをチェックして最終的な答えを返すようにする。ちなみにRPNとはReverse Polish Notationの略である。

参考

問題及び解法は以下の書籍を参考にさせていただいた。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

---

1. 逆ポーランド記法については以下を参照　逆ポーランド記法 ‐ 通信用語の基礎知識↩