Schemeで演算を行う

※ 以下はScheme初心者である私の勉強用のメモです。
間違っている可能性がありますので注意してください。

Schemeの演算は前置記法(ポーランド記法)で記述する。

例

1 + 2 ==> (+ 1 2)
1 + 2 + 3 ==> (+ 1 (+ 2 3))

なお、前置記法は任意個の引数の指定が可能である。したがって、(+ 1 (+ 2 3))は以下のように
書き直すことが出来る。

(+ 1 (+ 2 3)) = (+ 1 2 3)

 前置記法は上記の例のように単純な式であれば簡単に書くことができる。しかし、前置記法に慣れていないと、式が複雑になるにつれて書くことが難しくなる。そこで、日常で使い慣れた中置記法から前置記法に変換する方法を用いるとよい。中置記法から前置記法に変換するには、以下の2通りのやり方がある。

中置記法から前置記法への変換

• 優先順位順に括弧で囲んで演算子を前に出す。
  優先順位が同じなら左側にあるものを優先順が高いとみなす。(左結合)
• 構文木を作成し、深さ優先探索で項を拾う。

以下に例を示す。

例1

; 1 + 2 * 3 + 4を前置記法に変換する
STEP0: 1 + 2 * 3 + 4

; 優先順位を考慮して括弧で囲む
STEP1: ((1 + (2 * 3)) + 4)

; 優先順位の高い部分から、演算子を前に出す
STEP2: ((1 + (* 2 3)) + 4)
STEP3: ((+ 1 (* 2 3)) + 4)
STEP4: (+ 1 (* 2 3) 4)

例2

構文木を利用して、1 + 2 * 3 + 4を前置記法に変換する。

(+ (+ (1 (* 2 3) 4))) ⇒ (+ 1 (* 2 3) 4)