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

前回の記事はこちら。

今回は前回から引き続きスタックの活用方法を見ていく。スタックの活用方法の例題としてよく挙げられるのが「逆ポーランド記法の数式を計算する」という課題である¹。ということで実際に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. 逆ポーランド記法については以下を参照　逆ポーランド記法 ‐ 通信用語の基礎知識↩

Javascriptでスタックを実装する

Javascriptには組み込みのデータ構造としてスタックが実装されていないので実装してみる。とはいえスタックに必要な基本操作はArrayに実装されているので、実質的にはスタック風のラッパーを被せるだけで事足りる。

実際のコードは以下のようになる。

class Stack {
  constructor() {
    this._array = [];
  }

  push(val) {
    this._array.push(val);
  }

  pop() {
    return this._array.pop();
  }

  peek() {
    return this._array[this._array.length - 1];
  }

  isEmpty() {
    return this._array.length === 0;
  }

  get top() {
    return this._array.length;
  }
}

topは現在のスタックの最大要素の位置を返すものでスタックポインタというやつである。get topとすることでゲッターとして定義している。これによってtopへの再代入を防止して擬似的にプライベート変数のような扱いにできる。

定義したStackは以下のように使用できる。

const s = new Stack();
s.push(1);
s.push(2);
s.push(3);
console.log(s.top); // 3
console.log(s.pop()); // 3
console.log(s.top); // 2
console.log(s.peek()); // 2
console.log(s.top); // 2
console.log(s.pop()); // 2
console.log(s.pop()); // 1
console.log(s.pop()); // undefined
console.log(s.top); // 0
console.log(s.isEmpty()); // true

参考

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

スタック - Wikipedia

Javascriptで非破壊ソートを実装する

Javascriptで数値配列をソートする - 2:00am, Writing codeでも少し触れたが、JavascriptのArray.sortは破壊的なソートなので、配列そのものの値を変更してしまう。 それでも問題ない場合も多いかもしれないが、うっかり配列を破壊してしまうことにより問題が発生することもあるだろうし、その手のバグは往々にして発見しづらいので厄介だ。何よりFunctional Programming的な観点で言うと無駄な副作用の発生は極力避けたいところである。

ということで今回はJavascriptで非破壊ソートを実装してみる。

Array.slice()で配列をコピー

元の配列を変更しないようにするためには、元の配列をコピーしてコピー後の配列をソートすればよい。ざっと検索してみると数年前までは以下のようなArray.slice()でコピーした配列をソートすることで非破壊ソートするのが主流だった模様。

const arr = [3, 2, 8, 4, 6, 1, 3, 20, 14];
console.log(arr.slice().sort((a, b) => a - b)); // [ 1, 2, 2, 3, 3, 6, 7, 9, 12, 16, 22 ]
console.log(arr); // [ 3, 2, 8, 4, 6, 1, 3, 20, 14 ]

Object.assignで配列をコピー

ES6ではObject.assignメソッドによるオブジェクトのコピーができるようになったので、今後はこっちの書き方も目にする機会が増えてくると思われる。今回は配列のコピーだが実際にはオブジェクトのコピーをする場合に目にすることの方が多いはず。

const arr = [3, 2, 8, 4, 6, 1, 3, 20, 14];
console.log(Object.assign([], arr).sort((a, b) => a - b)); // [ 1, 2, 2, 3, 3, 6, 7, 9, 12, 16, 22 ]
console.log(arr); // [ 3, 2, 8, 4, 6, 1, 3, 20, 14 ]

Object.assignは第1引数のオブジェクトに第2引数の直接所有かつ列挙可能な要素をコピーする。上記の例では空の配列に第2引数の配列の全要素をコピーした新しい配列を呼び出し元に返すという意味になる。

参考

[Sy] JavaScriptのArrayをソートした結果が欲しいけど、元の配列もそのままキープしたい（非破壊的にソート） | Syntax Error. Array.sliceの仕様にも触れられており調べた中では一番わかりやすかった

Object.assign() - JavaScript | MDN

Javascriptで数値配列をソートする

Javascriptには標準でArray.sortおよびArray.reverseが実装されているのでお手軽にソートを実行できる。と思いきやこいつらは数値配列をソートする場合は意図しない結果となることがあるので注意が必要である。

Array.sortは文字列比較

JavascriptのArray.sortはデフォルトだと「数値比較」ではなく「文字列比較」で実行される。つまり数値配列に対して素朴にArray.sortを実行すると以下のようになる。

const a = [1, 2, 10, 3, 11, 20, 12];
console.log(a.sort()); // [ 1, 10, 11, 12, 2, 20, 3 ] !!!????

期待する結果は[1, 2, 3, 10, 11, 12, 20]だが実行結果は1の後に10、11、12と続いている。これは各要素が文字列として比較されるためである。期待通りの結果を得るためには文字列比較ではなく数値比較を行う必要がある。

Array.sortで降順ソート

Array.sortではカスタムのComparator関数を引数に渡すことで独自の比較ロジックを実行することが出来る。今回は最もベーシックな降順/昇順ソートを試す。ちなみにここではComparatorとしてES6のArrow operatorを使って関数を定義している。

const a = [1, 2, 10, 3, 11, 20, 12];
console.log(a.sort((a, b) => b - a)); // [ 20, 12, 11, 10, 3, 2, 1 ]

Array.sortで昇順ソート

const a = [1, 2, 10, 3, 11, 20, 12];
console.log(a.sort((a, b) => a - b)); // [ 1, 2, 3, 10, 11, 12, 20 ]

なおJavascriptのArray.sortは破壊的なソート¹なので注意する。

参考

JavaScriptで配列をソートする - もやもやエンジニア

Array.prototype.sort() - JavaScript | MDN

---

1. 配列自体の内容が変更される。↩

Javascriptで数値を2進数/8進数/16進数に変換する

プログラミング問題でありがちな「数値を2進数に変換してごにょごにょする」という処理をJavascriptでやる方法。検索してみても意外と日本語のまとまった情報が見つけられなかったので一通りまとめておく。

基数変換はNumber.toStringを使う

基本的にはNumberクラスのtoStringに指定したい基数を渡してやれば、その数値の2進数/8進数/16進数表現が得られる。

console.log(Number(13).toString(2)); // 1101
console.log((13).toString(8)); // 15

const num = 27;
console.log(num.toString(16)); // 1b
console.log(27.toString(16)); // SyntaxError

なおNumber.toStringの仕様的には2進数や16進数に限らず2〜32までの任意の基数を指定できるようである。

ちなみに上記の最後の例のとおり数値リテラルに対してはもちろん実行できないので注意が必要である。ただ一旦変数に入れると数値リテラルのはずなのに実行できているのは、多分実行時に暗黙の型変換(Javaで言うオートボクシング¹)的な処理が実行されてるんじゃないかと思われる。

負数の2進数変換

上記のコードは正の整数に対しては期待通りの動作をするが、負の整数で実行すると意図しない結果となる。

console.log(Number(-1).toString(2)); // -1

負数の場合でも意図通りの変換を行うためには、以下のようにビット演算子による32ビット変換をかけた後にtoString()する必要がある。

console.log((-1 >>> 0).toString(2)); // 11111111111111111111111111111111

負数は2の補数で表現される。

参考

how do I convert an integer to binary in javascript? - Stack Overflow

ビット演算子 - JavaScript | MDN

---

1. 【Java】オートボクシング、アンボクシング - Qiita↩

FizzBuzz in Javascript

みんな大好きFizzBuzzをJavascriptで書いてみる。とはいえJavascript固有の処理は関数のデフォルト引数ぐらいしかないので他の言語でも99%応用できる。

function fizzBuzz(begin = 1, end = 100) {
  for (let i = begin; i <= end; i++) {
    const isFizz = i % 3 === 0, isBuzz = i % 5 === 0;
    console.log(isFizz && isBuzz ? 'FizzBuzz!' : isFizz ? 'Fizz' : isBuzz ? 'Buzz' : i);
  }
}
fizzBuzz();

最も素朴な実装はif文で分岐するパターン¹だが、自分は上記のように説明変数を定義する方が好みだ。出力は3項演算子をチェインさせている。基本的に3項演算子のチェインはバッドプラクティスとされているけど、分岐条件が単純かつ明確で頭から読み下していける場合は別に使ってもいいんじゃないかなーと個人的には思っている²。

---

1. if (i % 3 === 0 && i % 5 === 0) { ~ってやつ↩

2. けど世間的にはどうなんだろか。やっぱイカンのかな。↩

Javascriptで文字列中に出現する各文字を数える

プログラミング問題などでありがちな、ある文字列内の任意の文字の出現数をカウントするという課題。Javascriptだとこんな感じに書ける。

function countCharInStr(str, chara) {
  const counts = {};
  for (let c of str) {
    counts[c] = c in counts ? counts[c] + 1 : 1;
  }
  return chara in counts ? counts[chara] : 0;
}

const str = 'aaaaaabbbcc';
const counts_a = countCharInStr(str, 'a');
console.log(counts_a); // 6

forループで文字列をループさせるC言語チックな書き方も出来るがlet a of b構文を使うと簡潔に書ける。オブジェクトのキーチェックはkey in obj構文で行っている。文字列のループ部分はES6環境ならspread演算子¹を使って以下のようにも書ける²。

function countCharInStr(str, chara) {
  const counts = {};
  [...str].map((c) => {
    counts[c] = c in counts ? counts[c] + 1 : 1;
  });
  return chara in counts ? counts[chara] : 0;
}

ちなみに各文字の全体の出現頻度(度数)が必要な場合はcountsオブジェクトをそのままreturnしてよしなにすればよい。

---

1. …(ドット3つ)というやつ。スプレッド演算子 - JavaScript | MDN↩

2. こっちの方が簡潔かも。まぁ好みの問題ではある。↩