リストと二分木

教えて!gooのC言語カテゴリにこんな問題が上がってた。

定数と演算記号（+または*）からなる数式を表現する二分木を使い、演算子の順序を交換する操作を考える。
二分木のノードとなる構造体は、

struct node { int type, val;
　　　　　　struct node *left, *right; };

とする。ノードの種類を type の値により区別する。数値を示すときは type を'v'とし、type が'o'のとき演算子であるとする。数値の場合には値を valに格納する。演算子（+と*の２種類のみ考える）のときは、val は'+'か'*'のいずれかにする。

各関数の役割を述べる。

関数 new_node は、ノードとなる構造体を malloc で確保し、各メンバーの値を引数から得た値から設定し、その構造体を戻り値とする。
関数 v_nodeは、引数で与えられた数値を表すノードを作成して返すものである。
関数 o_node は、演算子を表すノードを作成して返すもので、演算子の種類を第一引数で（'+'または'*'として）指定する。第二～第三引数に従って left ,right の値が設定される。
関数 calc は、引数で与えられた木について演算結果の値を返す。
関数 printTree は字下げをつけて二分木を右側ノードが上になるよう表示する。
関数changeNodes は引数で指定されたノードとその右のノードを交換する。

これらの関数を完成させることが課題である。

main では、二分木を作成したのち printTree で二分木を表示し、calc を用いて式の値を表示する。
さらに changeNodes を呼び出して演算子の順序を交換する。交換を行った後の二分木について printTree で二分木を表示し、calc を用いて式の値を表示している。

実行結果の例
$ ./a.out
初期状態
　　　　　　v:2
　　　op:+
　　　　　　v:1
op:*
　　　v:3
式の値：9
changeNodes 実行後
　　　v:2
op:+
　　　　　　v:1
　　　op:*
　　　　　　v:3
式の値：5

作成する２つの関数について詳しく述べる。

関数 printTree は以下のように作成せよ。
第二引数は字下げ量で、行の先頭からの空白の数を示す。
第一引数は表示させる木のノードで、それが NULL なら何もしない。NULL でなければ、以下①～③を行う。

①字下げを 3 増やして右部分木を表示する。
②引数で渡されたノードの値を表示する。この際に、ノードが数値であれば書式"v:%d"で val を表示し、ノードが演算子であれば書式"op:%c"で val を表示する。
③字下げを 3 増やして左部分木を表示する。

関数 changeNodes は以下のように作成せよ。
引数はノードの入れ替えを行う際に先頭とするノードxを示す。その右のノードyとの交換は、x が y の左になり、y の左であったものは x の右になる。x の左と y の右はそのままで、関数の戻り値は y になる。
なお、x または y が NULL の場合は何もせず x を返す。

この問題を初めて読んだ時、正直

「嫌な問題だな」

と思った。

もちろん、僕がC言語を嫌ってる、って事もあるんだけど、それより最初に思いついたのは

「Lispなら簡単なのに!」

である。

Lispなら簡単に書ける問題をわざわざC言語で書かなきゃいけない、ってのがどーにも嫌なのだ。

ちなみに、この問題のC言語での解答は例えば以下のようになる。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node {
　int type, val;
　struct node *left, *right;
};

typedef struct node* EXP;

EXP new_node(int t, int v, EXP l, EXP r) { /* ノードを作成し値を設定 */
　EXP x;
　x = (EXP)malloc(sizeof(struct node));
　if (x == NULL) {
　　printf("malloc failed");
　　exit(EXIT_FAILURE);
　}
　x->type = t;
　x->val = v;
　x->left = l;
　x->right = r;
　return x;
}

EXP v_node(int v) { 　　　　　　/* 数値ノード */
　return new_node('v', v, NULL, NULL);
}

EXP o_node(int o, EXP l, EXP r) { /* 演算子ノード */
　return new_node('o', o, l, r);
}

int calc(EXP e) { 　　　　　　　　/* 二分木で示される式の値を計算 */
　int rv, lv;
　if (e->type == 'v') {
　　return e->val;
　}
　rv = calc(e->right);
　lv = calc(e->left);
　if (e->type == 'o' && e->val == '+') {
　　return rv + lv;
　}
　if (e->type == 'o' && e->val == '*') {
　　return rv * lv;
　}
　return EXIT_SUCCESS; 　　/* デフォルト */
}

void printTree(EXP t, int ind) {
　char str[256];
　for (int i = 0; i <= ind; i++) {
　　if (i < ind) {
　　　str[i] = ' ';
　　} else {
　　　str[i] = '\0';
　　}
　}
　if (t == NULL) {
　　return;
　} else {
　　printTree(t->right, ind + 3);
　　t->type == 'v' ? strcat(str, "v:%d\n") : strcat(str, "op:%c\n");
　　printf(str, t->val);
　　printTree(t->left, ind + 3);
　}
}

EXP changeNodes(EXP t) {
　EXP x = (EXP)malloc(sizeof(struct node));
　EXP y = (EXP)malloc(sizeof(struct node));
　x = t;
　y = t->right;
　if (x == NULL || y == NULL) {
　　return x;
　} else {
　　x->right = y->left;
　　y->left = x;
　　return y;
　}
}

int main(void) {
　EXP n1, n2, n3;

　n2 = o_node('+', v_node(1), v_node(2));
　n1 = o_node('*', v_node(3), n2);
　printf("初期状態\n");
　printTree(n1, 0);
　printf("式の値 : %d\n", calc(n1));
　n1 = changeNodes(n1);
　printf("changeNodes 実行後\n");
　printTree(n1, 0);
　printf("式の値 : %d\n", calc(n1));

　n3 = o_node('+', v_node(1), v_node(2));
　n2 = o_node('*', v_node(3), n3);
　n1 = o_node('*', v_node(4), n2);
　printf("初期状態\n");
　printTree(n1, 0);
　printf("式の値 : %d\n", calc(n1));
　n1->right = changeNodes(n1->right);
　printf("changeNodes-1 実行後\n");
　printTree(n1, 0);
　printf("式の値 : %d\n", calc(n1));
　n1 = changeNodes(n1);
　printf("changeNodes-2 実行後\n");
　printTree(n1, 0);
　printf("式の値 : %d\n", calc(n1));
　return EXIT_SUCCESS;
}

まぁ、C言語にそんなに詳しくない人はそこまで読み込まなくていい。

ただ、冒頭の

struct node {
　int type, val;
　struct node *left, *right;
};

は完全に同じではないが、殆どLispのリストである。

逆に言うと、C言語でLispを書く場合、殆どこれと同じモノがリストとして実装されている。

要するに、Lispにはこれとほぼ同一のモノがビルトインで用意されてるわけで、こんなに長くコードを弄らなくて良いのだ。

structはユーザー定義型を定義する機能だ。

C言語でのユーザー定義型を構造体と呼ぶ。

構造体は、ぶっちゃけ、配列と殆ど同じなのだが、配列は要素番号で値にアクセスするが、構造体では要素に名前を付ける事が出来る。

上の構造体の定義は、Pythonで言うと殆ど

class node:
　def __init__(self, t, v, l, r):
　　self.type = t
　　self.val = v
　　self.left = l
　　self.right = r

と同じである。

さて、二分木であるが、これは木構造、と言うデータ構造の一種である。

例えば上で挙げられてる例を見てみよう。

　　　　　　v:2
　　　op:+
　　　　　　v:1
op:*
　　　v:3

これは図示すると次を意味している。

逆さまになってるが、*が木の根だとするとそこから「二つに分かれた」枝で構成されてる木に見えないだろうか。

まぁ、だから「木構造」と言うのであり、また「枝が二つにしか分かれない」前提なので二分木と呼んでいる。

また、二つに分かれる直前の「値」が節なのだが、この節をカッコつけて「ノード」と言う。

そして枝を「エッジ」、また最初のノード、この場合は*だが、これを根、または「ルート」と呼ぶ。

用語的にはこれだけ、だ。ルート、エッジ、ノード、の3つだけ覚えておけば良い。

ところで、上の二分木の例なんだけど、もうこれは実はこのままLispで書き表す事が出来る。

つまりこうだ。

(* 3 (+ 1 2))

これだけだ。もう、演算子が最初に来る、って言う対応も上の二分木と同じである。

もうちょっと二分木っぽく表現すれば、

(* 3
　(+ 1
　　2))

かな。

ノード左
　　　右

と言う事なんだが。

見事にお題を表してる、と思わないだろうか。

なんでこんなに表現が酷似してるんだろう。

タネを明かすと、元々、例題のような「状況」を何が作るのか、と言うとプログラミング言語の構文解析が作る、ってのが殆どなのだ。

例えばフツーの1 + 2とか入力した場合、殆どのケースではプログラミング言語内だとLispみたいに + 1 2 の語順に直したり、あるいはLispの逆である 1 2 + に直したりする。

一方、Lispは、言い方を変えると、Pythonみたいなinputは持たない。Lispのリーダーは剥き出しの構文解析器である。

だからLispを使ってる奴らは「プログラミング言語としての」Lispの文法なんざ入力しない。いきなり構文解析器に「読ませる」式を入力し、それが(+ 1 2)と言う表現なのだ。

結果、「構文解析器が作るべき」二分木と、Lispでの「数式表現」が似通ってるのは、偶然でも何でもない。

むしろ「必然」なのである。

Lispでの二分木の基本的な書き方は

(ノード左右)

となる。

だから僕らはRacket等のLispを使う限り、構造体でデータ設計、なんつーややこしい事はしないで、問題に従うと、直接関数new-nodeを次のように書き下す事が出来る。

(define (new-node type val left right)
　`(,val ,left ,right))

これを利用すれば、数値用のv-node関数、演算子用のo-node関数、はすぐでっち上げる事が出来る。

(define (v-node v)
　(new-node v #f #f))

(define (o-node o l r)
　(new-node o l r))

C言語原版にあるtype引数は特に必要がない(※1)。

> (define *n2* (o-node '+ (v-node 1) (v-node 2)))
> (define *n1* (o-node '* (v-node 3) *n2*))
> *n1*
'(* (3 #f #f) (+ (1 #f #f) (2 #f #f)))
> *n2*
'(+ (1 #f #f) (2 #f #f))
>

そしてC言語原版でも再帰で書かれてる木の表示用printTree関数も、再帰なら任せろ、とばかりにRacketではハナクソをほじりながら書くことが出来る。

(define (printTree t ind)
　(let ((indent (make-string ind #\space)))
　　(when t
　　　(printTree (caddr t) (+ ind 3))
　　　(let ((val (car t)))
　　　　(format #t "~a~a~a~%" indent (if (symbol? val)
　　　　　　　　　　　　　　　　　　　"op:"
　　　　　　　　　　　　　　　　　　　"v:") val))
　　　(printTree (cadr t) (+ ind 3)))))

ここではSRFI-48のformatを使用している。

また、Schemeには文字列生成の関数(make-string)が備わっている為、インデント幅を調整する為にわざわざルーピングする必要がない。

> (printTree *n1* 0)
　　　　v:2
　　op:+
　　　　v:1
op:*
　　v:3
>

ノードを交換するchangeNodes関数を書くのも簡単だ。

(define (changeNodes t)
　(let ((x t) (y (caddr t)))
　　(if (and x y)
　　　`(,(car y) (,@(take x 2) ,(cadr y)) ,(caddr y))
　　　x)))

C言語のようにポインタを使って長たらしく書く必要はない。単に、問題文に従ってリストの要素を交換するだけ、である。

ここではSRFI-1のtakeを用いた。

> (printTree (changeNodes *n1*) 0)
　　v:2
op:+
　　　　v:1
　　op:*
　　　　v:3
>

残りは実値を計算するcalc関数だけ、である。

C言語版でも再帰を用いてるが、Lispが得意なのも再帰なんで、移植はメチャクチャ簡単である。

(define (calc e)
　(let ((type (car e)))
　　(cond ((eq? type '+) (+ (calc (caddr e)) (calc (cadr e))))
　　　　　((eq? type '*) (* (calc (caddr e)) (calc (cadr e))))
　　　　　(else type))))

これだけで終わり、だ。