TypeScript入門 第2回 逆ポーランド記法

目次

新しいプログラミング言語の勉強を始める時は, 簡単なプログラムを作成するようにしており, 逆ポーランド記法（Reverse Polish Notation, RPN）で書かれた数式を計算するプログラムを作成することから始めています. 逆ポーランド記法に馴染みのない方もおられると思うので, 逆ポーランド記法の説明から始めます. なお, 記事が長くなるので分割します. 

１）逆ポーランド記法

多くのプログラミング言語では, 算数や数学の授業で習った数式と同じ形式で数式を書きます. 例えば, ２と３の足し算は次のように書きます.

２＋３

この式に４を掛けてみます.

（２＋３）×４

２＋３×４

「２＋３」全体に４を掛ける場合と３だけに４を掛ける場合とで計算結果は異なります. 一般に使う数式では, 次の事柄を把握しておかないと計算結果がとんでもないことになります.

1. ＋や×などの演算子の優先順位
2. カッコの有無や入れ子の具合

通常の数式では, ＋や×などの演算子は数字と数字の間に置きますが, 逆ポーランド記法では演算子を最後に置きます. 例えば, 「２＋３」を次のように書きます.

２　３　＋

「２に３を足す」と日本語の語順通りに読めます. 同じようにして, 「（２＋３）×４」と「２＋３×４」も逆ポーランド記法で書いてみます.

２　３　＋　４　×

２　３　４　×　＋

上の式は「２に３を足して, その結果に４を掛ける」, 下の式は「２に, ３と４を掛けた結果を足す」と読めます. 賢明なる読者の皆様はすでにお気づきの通り, 逆ポーランド記法で書いた式にはカッコが現れていません. また, 演算子の優先順位も考えなくて済みます. 

２）スタック

逆ポーランド記法で記述した式を計算する手順, 即ちアルゴリズムを考えていきたいのですが, その前にスタック（Stack）と呼ばれるデータ構造を確認する必要があります.

スタックは, 机の上に積んだ本をイメージすると分かりやすいと思います. 

スタックに対して行える操作は次の２つです.

1. プッシュ（Push）：積んである本（つまり, スタック）に新しい本を載せる.
2. ポップ（Pop）：スタックの１番上の本を取る.

スタックでは, 一番上に積んである本に対してのみ働きかけられ, 途中の本については何もできません. スタックの一番底にある本を取り出すためには, １番上にある本から順に取り除く必要があります. 

３）アルゴリズム

スタックを用いれば, 逆ポーランド記法で記述した式を計算するアルゴリズムを簡潔に述べられます. 

1. 式を構成する数値や演算子といった要素を順番に処理します.
2. 数値の場合, スタックにプッシュします.
3. 演算子の場合, スタックから数値を２つポップし, 演算子に応じた計算をした結果をスタックにプッシュします.
4. 式の終端に到達した場合, スタックには１つだけ数値が残っており, その数値が求める答えです. 
5. 計算の途中で空になったスタックからポップした場合や, 最後に２つ以上の数値がスタックに残っている場合, 不正な式と判断できます. 

４）試してみる

TypeScriptの配列をスタックとして使うためのpushメソッドとpopメソッドがあります. これらを使ってアルゴリズムを試してみます. 

まず, TypeScriptのプロジェクトを作成します. ディレクトリ名は逆ポーランド記法ということで「RPN」としています. プロジェクトの作成方法については, 前回の記事を参照してください. とりあえず, 関数の定義とかも考えず, 入力となる式もソースコードに埋め込んで, 計算できるものを作ります. でき上ったプログラムは次の通りです.

console.log('逆ポーランド記法')

// 入力となる式

let input = ['2', '3', '+', '4', '*']

console.log('入力', input)

// 計算のためのスタック

let stack: number[] = []

console.log('スタック', stack)

console.log('計算開始')

for (let value of input) {

    console.log('入力値', value)

    if (value === '+') {

        let a = stack.pop()

        let b = stack.pop()

        // let c = a + b

        if ('number' === typeof a && 'number' === typeof b) {

            stack.push(a + b)

        } else {

            throw new Error('数字が入ってないよ')

        }

    } else if (value === '*') {

        let a = stack.pop()

        let b = stack.pop()

        if ('number' === typeof a && 'number' === typeof b) {

            stack.push(a * b)

        } else {

            throw new Error('数字が入ってないよ')

        }

    } else {

        let a = parseInt(value)

        stack.push(a)

    }

    console.log('スタック', stack)

}

console.log('計算終了')

console.log('スタック', stack)

コンパイルして実行してみます.

PS C:\TSWork\RPN> .\node_modules\.bin\tsc
PS C:\TSWork\RPN> node .\dist\index.js
逆ポーランド記法
入力 [ '2', '3', '+', '4', '*' ]
スタック []
計算開始
入力値 2
スタック [ 2 ]
入力値 3
スタック [ 2, 3 ]
入力値 +
スタック [ 5 ]
入力値 4
スタック [ 5, 4 ]
入力値 *
スタック [ 20 ]
計算終了
スタック [ 20 ]
PS C:\TSWork\RPN>

期待通りの結果が得られました.

ソースコードでは, 演算子が入力された場合, スタックから数値をポップしています. この時, スタックが空の場合があるため, ポップした結果がundefinedである可能性があります. そのまま計算しようとすると, TypeScriptに怒られてしまいます.

TypeScriptのコンパイラ報告するエラーは事前に潰さなくてはコンパイルすらできません. TypeScriptでは, このようなコンパイル時のエラーに対応するためのソースコードを丁寧に書いて, コンパイラを納得させてからようやく実行できます. これが煩わしく感じられる人もいると思いますが, リリース後にこのような不具合が見つかることを考えると, コンパイラのご機嫌を取るぐらい何ともありません. 逆に, 慣れてくるとコンパイラのチェックの甘いプログラミング言語は怖くて使えなくなります.

ソースコードはコピペしてもらっても良いのですが, 自分で入力することをお勧めします. 自分で入力することでコンパイラの応答を観察できるので, 理解がより深まります. 

５）まとめ

今回の記事では, 逆ポーランド記法で記述した式を計算するためのアルゴリズムを確認しました. 次回の記事では, 作成したプログラムをそれらしく仕上げていきます.

最後に, この記事で使用したNode.jsとTypeScriptのバージョンは次の通りです.

PS C:\TSWork\RPN> node --version

v14.17.5

PS C:\TSWork\RPN> .\node_modules\.bin\tsc --version

Version 4.3.5

PS C:\TSWork\RPN>

 目次