教えて!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言語のようにポインタを使って長たらしく書く必要はない。単に、問題文に従ってリストの要素を交換するだけ、である。
> (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))))
これだけで終わり、だ。
> (calc *n1*)
9
> (calc (changeNodes *n1*))
5
>
ノード交換前とノード交換後の計算結果が違う、と言うのも一目瞭然だ。
なお、末尾再帰じゃないの?って思うかもしれないが、残念ながらこのケースは末尾再帰には変換出来ない。
いや、厳密には継続受け渡し方式なら末尾再帰で書けるが、書けても最適化は成されないケースである。
一般に、木構造を辿る際、特に二分木だとノードとエッジの最小構成が再帰的に木構造を形成してるので、再帰プログラミングとは相性が良いのだが、反面、末尾再帰が役に立たない構造でもある。
とまぁ、二分木の取扱いはLispの方が遥かに簡単である。
それを知ってると「C言語で二分木なんて・・・・・・」と不当な事をついつい思ってしまう、と言うお話である。
※1: C言語は変数宣言する際に一々型を付けなければならない性的静的型付け言語と言われる言語の一種だが、間抜けな事にLispのような「型判定述語」が用意されていない。
従って、持ってるデータを判別する手段が無いので、原版では「タグ」項目を付けて数値なのか文字なのかを分類せざるを得ない。
