文字列プログラミングのススメ

main.md

皆さんおはようございます。この記事はポエムアドベントカレンダー3日目です。

この記事では全ての変数をchar*型で扱うことの利点、またchar*型で扱うデモンストレーションを行っていきます。

#変数がchar*型であるということの利点について考える C++において変数がchar*型であるということを否定的に捉える人もいるかと思います。 特にTMPなどの静的言語を使ってきた人にとっては、char*しかないということが不安材料として目に映ることが多いのではないかと思います。

けれども、char*しかないということは、本当に素晴らしいことです。 char*しかないことによって、たくさんの面倒から開放されるからです。 ##どのような値でも代入できる まず基本的なこととして文字列にすればどのような値でも代入できるということです。 つまり、受け取るときにどのような型の値を受け取るのかを意識する必要がありません。

char* str = "Hage";
char* num = "123";
char* nums = "[1, 2, 3]";
char* person = "{age: 21, name: plasma}";

文字列であろうと、数値であろうと、配列であろうと、連想配列であろうと、それを意識する必要がありません。 ##記述量がとても短くなる char*であることによって記述量がとても短くなります。

char* v="{{{1, 2, 3, 4, 5}}}";

もしchar*でなければ、次のようになるでしょう(STLの例)。

std::list<std::vector<std::array<int, 5>>> v=std::list<std::vector<std::array<int, 5>>>(std::vector<std::array<int, 5>>(std::array<int, 5>{1, 2, 3, 4, 5}));

##変更に強い 変数がchar*型だとソースコードの変更に強くなります。例えば右辺の返す値の仕様に変更があったとしても、受け取る側のソースコードを変更する必要はありません。

//clientはchar*であればよい
char* s = do_something();

##関数のオーバーロードが不要になる 説明不要ですね。 ##どのような値が代入されているかわからないという批判に答える 文脈を追って読むとどんな値が入っているかが、大抵はすぐにわかります。
そうでなくても文字列なのでprintfすればすぐにわかります。 ##変数に型がないことのデメリットはないのか あげるとすれば、パフォーマンスです。値の型が事前にわかっていれば、数値演算は圧倒的に早くなります。 char*型ではコンパイル時での計算が難しいのでその分実行時間が長くなります。 でもパフォーマンスが問題にならない局面ではchar*型を利用するのがよいと思います。

もう一つは実装次第ではバッファオーバーランの可能性を孕むことです。これは諦めてください。 #char*型で整数計算を行う char*型での整数計算では「小学校で習った筆算をコンピュータに行わせる方法」と「インクリメント関数を複数回呼ぶ方法」の2つが存在します。 共通で数値の最後尾がどれかを検索する関数が必要となるのでそれを実装します。

char* last(char* num)
{
	for (; *num != '\0'; ++num);
	return --num;
}

後者は実装が非常に軽いのでまずそちらから紹介します。
まず0であるかどうかを判別する関数を書きます。

char* is_zero(char* num)
{
	for(;*num!='\0', ++num)//文字列の末尾に達するまで繰り返す
		if(*num!='0')return "false";//0でない文字が出たらfalseを返す
	return "true";//0でない文字がないのでtrueを返す
}

次にインクリメントとデクリメントを行う関数を書きます。ここで'0'から'8'はインクリメントをすると一つ数値が大きくなり、'1'から'9'はデクリメントをすると一つ数値が小さくなる事実を使います。

void increment(char* num)
{
	char* ptr = last(num);
	for (; ptr != num; --ptr) {
		if (*ptr == '9')*ptr = '0';//今指してる桁が9なら0にする
		else { ++(*ptr); return; }//そうでないならインクリメントして終了する
	}
	++(*num);
}
void decrement(char* num)
{
	char* ptr = last(num);
	for(; ptr != num; --ptr){
		if(*ptr=='0')*ptr='9';//今指してる桁が0なら9にする
		else{--*ptr; return;}//そうでないならデクリメントして終了する
	}
	--(*num);
}

あとは片方の数値を減らしつつもう片方の数値を増やすだけです。

char* sum(char* a, char* b)
{
	//元の文字列を変更しないようにローカルにコピーする
	char* _a = new char[strlen(a)+1];
	char* _b = new char[strlen(b)+1];
	strcpy(_a, a);
	strcpy(_b, b);
	
	for(;strcmp(is_zero(_b), "false")==0; decrement(_b))
		increment(_a);//_bが0になるまで_aのインクリメントを繰り返す
	delete _b;
	return _a;
}

この実装の問題点はパフォーマンスが非常に悪いということです。メモリに対して計算時間が指数関数オーダーになっています。

一方前者の実装ならパフォーマンスがかなりよくなります。次はこちらの実装を紹介します。
まず2つの'0'から'9'を足し算した結果がどうなるかを返す関数を作ります。上のincrementを使う実装もありますがここはswitchを用いて直接書きます。

char sum_char(char a, char b, char* result)//resultに繰り上がりの有無を書く
{
	switch (a) {
	case '0':switch (b) {
	case '0':strcpy(result, "false");return '0';
	case '1':strcpy(result, "false");return '1';
	case '2':strcpy(result, "false");return '2';
	case '3':strcpy(result, "false");return '3';
	case '4':strcpy(result, "false");return '4';
	case '5':strcpy(result, "false");return '5';
	case '6':strcpy(result, "false");return '6';
	case '7':strcpy(result, "false");return '7';
	case '8':strcpy(result, "false");return '8';
	case '9':strcpy(result, "false");return '9';
	}
	case '1':switch (b) {
	case '0':strcpy(result, "false");return '1';
	case '1':strcpy(result, "false");return '2';
	case '2':strcpy(result, "false");return '3';
	case '3':strcpy(result, "false");return '4';
	case '4':strcpy(result, "false");return '5';
	case '5':strcpy(result, "false");return '6';
	case '6':strcpy(result, "false");return '7';
	case '7':strcpy(result, "false");return '8';
	case '8':strcpy(result, "false");return '9';
	case '9':strcpy(result, "true");return '0';
	}
	case '2':switch (b) {
	case '0':strcpy(result, "false");return '2';
	case '1':strcpy(result, "false");return '3';
	case '2':strcpy(result, "false");return '4';
	case '3':strcpy(result, "false");return '5';
	case '4':strcpy(result, "false");return '6';
	case '5':strcpy(result, "false");return '7';
	case '6':strcpy(result, "false");return '8';
	case '7':strcpy(result, "false");return '9';
	case '8':strcpy(result, "true");return '0';
	case '9':strcpy(result, "true");return '1';
	}
	case '3':switch (b) {
	case '0':strcpy(result, "false");return '3';
	case '1':strcpy(result, "false");return '4';
	case '2':strcpy(result, "false");return '5';
	case '3':strcpy(result, "false");return '6';
	case '4':strcpy(result, "false");return '7';
	case '5':strcpy(result, "false");return '8';
	case '6':strcpy(result, "false");return '9';
	case '7':strcpy(result, "true");return '0';
	case '8':strcpy(result, "true");return '1';
	case '9':strcpy(result, "true");return '2';
	}
	case '4':switch (b) {
	case '0':strcpy(result, "false");return '4';
	case '1':strcpy(result, "false");return '5';
	case '2':strcpy(result, "false");return '6';
	case '3':strcpy(result, "false");return '7';
	case '4':strcpy(result, "false");return '8';
	case '5':strcpy(result, "false");return '9';
	case '6':strcpy(result, "true");return '0';
	case '7':strcpy(result, "true");return '1';
	case '8':strcpy(result, "true");return '2';
	case '9':strcpy(result, "true");return '3';
	}
	case '5':switch (b) {
	case '0':strcpy(result, "false");return '5';
	case '1':strcpy(result, "false");return '6';
	case '2':strcpy(result, "false");return '7';
	case '3':strcpy(result, "false");return '8';
	case '4':strcpy(result, "false");return '9';
	case '5':strcpy(result, "true");return '0';
	case '6':strcpy(result, "true");return '1';
	case '7':strcpy(result, "true");return '2';
	case '8':strcpy(result, "true");return '3';
	case '9':strcpy(result, "true");return '4';
	}
	case '6':switch (b) {
	case '0':strcpy(result, "false");return '6';
	case '1':strcpy(result, "false");return '7';
	case '2':strcpy(result, "false");return '8';
	case '3':strcpy(result, "false");return '9';
	case '4':strcpy(result, "true");return '0';
	case '5':strcpy(result, "true");return '1';
	case '6':strcpy(result, "true");return '2';
	case '7':strcpy(result, "true");return '3';
	case '8':strcpy(result, "true");return '4';
	case '9':strcpy(result, "true");return '5';
	}
	case '7':switch (b) {
	case '0':strcpy(result, "false");return '7';
	case '1':strcpy(result, "false");return '8';
	case '2':strcpy(result, "false");return '9';
	case '3':strcpy(result, "true");return '0';
	case '4':strcpy(result, "true");return '1';
	case '5':strcpy(result, "true");return '2';
	case '6':strcpy(result, "true");return '3';
	case '7':strcpy(result, "true");return '4';
	case '8':strcpy(result, "true");return '5';
	case '9':strcpy(result, "true");return '6';
	}
	case '8':switch (b) {
	case '0':strcpy(result, "false");return '8';
	case '1':strcpy(result, "false");return '9';
	case '2':strcpy(result, "true");return '0';
	case '3':strcpy(result, "true");return '1';
	case '4':strcpy(result, "true");return '2';
	case '5':strcpy(result, "true");return '3';
	case '6':strcpy(result, "true");return '4';
	case '7':strcpy(result, "true");return '5';
	case '8':strcpy(result, "true");return '6';
	case '9':strcpy(result, "true");return '7';
	}
	case '9':switch (b) {
	case '0':strcpy(result, "false");return '9';
	case '1':strcpy(result, "true");return '0';
	case '2':strcpy(result, "true");return '1';
	case '3':strcpy(result, "true");return '2';
	case '4':strcpy(result, "true");return '3';
	case '5':strcpy(result, "true");return '4';
	case '6':strcpy(result, "true");return '5';
	case '7':strcpy(result, "true");return '6';
	case '8':strcpy(result, "true");return '7';
	case '9':strcpy(result, "true");return '8';
	}
	}
	return '0';
}

足し算の筆算の方法は皆さんご存知の通りですね。 ここでは「最上位から計算していき下位で繰り上がりが発生したらそれより大きい桁の部分をインクリメントする」という方式でいきます。

char* sum(char* a, char* b)
{
	if (strlen(a)<strlen(b))sum(b, a);//aの桁数の方が大きいように調整
	char* ret = new char[strlen(a) + 1]{};
	char* _b = last(b);
	++_b;
	for (char* ptr = a; b != _b; ++ptr)
	{
		if (_b - b <= strlen(a))
		{
			char r[6] = {};//C++なので先頭に0はいりません
			char c = sum_char(*ptr, *b, r);
			if (strcmp(r, "true") == 0)increment(ret);
			ret[ptr - a] = c;
		}
		else
		{
			ret[ptr - a] = *ptr;
		}
		++b;
	}
	return ret;
}

これで完成です。すぐに使えるようにひとまとまりにして書いておきます。

char* last(char* num)
{
	for (; *num != '\0'; ++num);
	return --num;
}

void increment(char* num)
{
	char* ptr = last(num);
	for (; ptr != num; --ptr) {
		if (*ptr == '9')*ptr = '0';//今指してる桁が9なら0にする
		else { ++(*ptr); return; }//そうでないならインクリメントして終了する
	}
	++(*num);
}

char sum_char(char a, char b, char* result)//resultに繰り上がりの有無を書く
{
	switch (a) {
	case '0':switch (b) {
	case '0':strcpy(result, "false");return '0';
	case '1':strcpy(result, "false");return '1';
	case '2':strcpy(result, "false");return '2';
	case '3':strcpy(result, "false");return '3';
	case '4':strcpy(result, "false");return '4';
	case '5':strcpy(result, "false");return '5';
	case '6':strcpy(result, "false");return '6';
	case '7':strcpy(result, "false");return '7';
	case '8':strcpy(result, "false");return '8';
	case '9':strcpy(result, "false");return '9';
	}
	case '1':switch (b) {
	case '0':strcpy(result, "false");return '1';
	case '1':strcpy(result, "false");return '2';
	case '2':strcpy(result, "false");return '3';
	case '3':strcpy(result, "false");return '4';
	case '4':strcpy(result, "false");return '5';
	case '5':strcpy(result, "false");return '6';
	case '6':strcpy(result, "false");return '7';
	case '7':strcpy(result, "false");return '8';
	case '8':strcpy(result, "false");return '9';
	case '9':strcpy(result, "true");return '0';
	}
	case '2':switch (b) {
	case '0':strcpy(result, "false");return '2';
	case '1':strcpy(result, "false");return '3';
	case '2':strcpy(result, "false");return '4';
	case '3':strcpy(result, "false");return '5';
	case '4':strcpy(result, "false");return '6';
	case '5':strcpy(result, "false");return '7';
	case '6':strcpy(result, "false");return '8';
	case '7':strcpy(result, "false");return '9';
	case '8':strcpy(result, "true");return '0';
	case '9':strcpy(result, "true");return '1';
	}
	case '3':switch (b) {
	case '0':strcpy(result, "false");return '3';
	case '1':strcpy(result, "false");return '4';
	case '2':strcpy(result, "false");return '5';
	case '3':strcpy(result, "false");return '6';
	case '4':strcpy(result, "false");return '7';
	case '5':strcpy(result, "false");return '8';
	case '6':strcpy(result, "false");return '9';
	case '7':strcpy(result, "true");return '0';
	case '8':strcpy(result, "true");return '1';
	case '9':strcpy(result, "true");return '2';
	}
	case '4':switch (b) {
	case '0':strcpy(result, "false");return '4';
	case '1':strcpy(result, "false");return '5';
	case '2':strcpy(result, "false");return '6';
	case '3':strcpy(result, "false");return '7';
	case '4':strcpy(result, "false");return '8';
	case '5':strcpy(result, "false");return '9';
	case '6':strcpy(result, "true");return '0';
	case '7':strcpy(result, "true");return '1';
	case '8':strcpy(result, "true");return '2';
	case '9':strcpy(result, "true");return '3';
	}
	case '5':switch (b) {
	case '0':strcpy(result, "false");return '5';
	case '1':strcpy(result, "false");return '6';
	case '2':strcpy(result, "false");return '7';
	case '3':strcpy(result, "false");return '8';
	case '4':strcpy(result, "false");return '9';
	case '5':strcpy(result, "true");return '0';
	case '6':strcpy(result, "true");return '1';
	case '7':strcpy(result, "true");return '2';
	case '8':strcpy(result, "true");return '3';
	case '9':strcpy(result, "true");return '4';
	}
	case '6':switch (b) {
	case '0':strcpy(result, "false");return '6';
	case '1':strcpy(result, "false");return '7';
	case '2':strcpy(result, "false");return '8';
	case '3':strcpy(result, "false");return '9';
	case '4':strcpy(result, "true");return '0';
	case '5':strcpy(result, "true");return '1';
	case '6':strcpy(result, "true");return '2';
	case '7':strcpy(result, "true");return '3';
	case '8':strcpy(result, "true");return '4';
	case '9':strcpy(result, "true");return '5';
	}
	case '7':switch (b) {
	case '0':strcpy(result, "false");return '7';
	case '1':strcpy(result, "false");return '8';
	case '2':strcpy(result, "false");return '9';
	case '3':strcpy(result, "true");return '0';
	case '4':strcpy(result, "true");return '1';
	case '5':strcpy(result, "true");return '2';
	case '6':strcpy(result, "true");return '3';
	case '7':strcpy(result, "true");return '4';
	case '8':strcpy(result, "true");return '5';
	case '9':strcpy(result, "true");return '6';
	}
	case '8':switch (b) {
	case '0':strcpy(result, "false");return '8';
	case '1':strcpy(result, "false");return '9';
	case '2':strcpy(result, "true");return '0';
	case '3':strcpy(result, "true");return '1';
	case '4':strcpy(result, "true");return '2';
	case '5':strcpy(result, "true");return '3';
	case '6':strcpy(result, "true");return '4';
	case '7':strcpy(result, "true");return '5';
	case '8':strcpy(result, "true");return '6';
	case '9':strcpy(result, "true");return '7';
	}
	case '9':switch (b) {
	case '0':strcpy(result, "false");return '9';
	case '1':strcpy(result, "true");return '0';
	case '2':strcpy(result, "true");return '1';
	case '3':strcpy(result, "true");return '2';
	case '4':strcpy(result, "true");return '3';
	case '5':strcpy(result, "true");return '4';
	case '6':strcpy(result, "true");return '5';
	case '7':strcpy(result, "true");return '6';
	case '8':strcpy(result, "true");return '7';
	case '9':strcpy(result, "true");return '8';
	}
	}
	return '0';
}

char* sum(char* a, char* b)
{
	if (strlen(a)<strlen(b))sum(b, a);//aの桁数の方が大きいように調整
	char* ret = new char[strlen(a) + 1]{};
	char* _b = last(b);
	++_b;
	for (char* ptr = a; b != _b; ++ptr)
	{
		if (_b - b <= strlen(a))
		{
			char r[6] = {};//C++なので先頭に0はいりません
			char c = sum_char(*ptr, *b, r);
			if (strcmp(r, "true") == 0)increment(ret);
			ret[ptr - a] = c;
		}
		else
		{
			ret[ptr - a] = *ptr;
		}
		++b;
	}
	return ret;
}

早速試してみましょう。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

//途中省略

int main()
{
	std::cout<<sum("12345678987654321", "11111111111111111")<<std::endl;
}

ちゃんと計算できましたね。この関数はint型では計算出来ないような大きな数字も計算できます。 #まとめ この記事では以下のことをしました。
・char*型でC++のプログラムを書こう
・char*型でできる整数計算
この記事を通してchar*型でプログラムを書く方が増えることを願っています。

ファックなので星5です

ファックなので星5です