こんにちはSayahamittです。
さて今回はC言語で逆ポーランド記法(スペース区切り)電卓を作ってみました。
文字列の動的確保とか、リストでスタックを実装したりとかしたので備忘録として残しておこうと思います。
(…Twitterクライアント?…(やってますよ…OOPとC++難しい…))
仕様っぽいもの
今回作った電卓では、四則演算が逆ポーランド記法(スペース区切り)によって書かれた数式を文字列入力として受け取り、スタックを利用して計算することにしました。和差積商以外の演算や関数はエラーを返すこととします。
また、入力桁数に制限があるとつまらないので、mallocを使って文字配列を動的確保し、
それに伴いスタックも双方向リストを用いて動的に伸縮できるように実装することとしました。
動的確保のアルゴリズムは、文字列を伸ばす場合には容量が増えた後の全体を格納するのに必要なメモリを丸々全部確保し直すものとしました。
完動コードへのリンク RPNcalc.c (Gists)
目次
- 入力受付と文字列動的確保
- リストによるスタックの実装
- 四則演算の実装
入力受付と文字列の動的確保
char* v_input(){
char* input = malloc(10);
char* tempCopy;
char tempIn[10];
unsigned int InputSize;
for(InputSize=10;strchr(tempIn,'=')==NULL;InputSize+=10){
fgets(tempIn,10,stdin);
tempCopy = malloc(InputSize);
strcpy(tempCopy,input);
free(input);
input = malloc(InputSize);
strcpy(input,tempCopy);
strcat(input,tempIn);
free(tempCopy);
}
return input;
}
キーボードで入力された文字列を受け取る関数です。
この関数では入力文字列の長さに応じて必要な分だけメモリを確保して文字列を作成し、返しています。
手順のイメージ
詳しい手順を文章で書くとソースコードをそのまま日本語にすることになるのでここではイメージだけ書きます。
標準入力から一定長ずつ文字列を読み取って、それまでに読み取った文字列に付け加えていき、その度に累積した文字列の長さ分のメモリ領域を丸々新しく確保し直しています。上のコードでは10文字毎なので、大まかな手順は以下のようなループになります。
1.10文字分のメモリ領域を確保しておく。
2.標準入力ストリームから10文字読み込み 1 で確保したメモリ領域に書き込む。
3.一回前のループまでで読んだ文字列長 + 10文字分 のメモリ領域を新たに確保する。
4. 3 で確保したメモリ領域に 一回前のループまでで読んだ文字列(一回前の5の文字列) をコピーする。
5. 4 の文字列に 2 の文字列(10文字)を付け加える。
6. 2 に戻る。
今回はこの処理を ‘=’ を読み込むまで続けます。実際には、コピー処理そのものに必要なメモリ領域の確保や、一回前のループで確保したメモリ領域の開放などが必要になりますが、イメージとしては大体こんなもんです。
リストによるスタックの実装
//ノード構造体
typedef struct double_stack_node{
struct double_stack_node* upper;
struct double_stack_node* lower;
double value;
} double_stack_node;
//スタック作成、初期化関数
double_stack_node* create_stack(){
double_stack_node* base_node = malloc(sizeof(double_stack_node));
base_node->lower = NULL;
base_node->upper = NULL;
base_node->value = 0;
return base_node;
}
//スタックに積まれている値を上から全て表示する
void show_stack(double_stack_node* stack){
double_stack_node* pointer = stack;
int i;
for(i=0;pointer->lower != NULL;pointer = pointer->lower){
printf("%d段目:%f\n",++i,pointer->value);
}
}
//プッシュ関数
void push(double_stack_node** p_stack,double value){
double_stack_node* nw_node = malloc(sizeof(double_stack_node));
nw_node->value = value;
nw_node->lower = (*p_stack);
nw_node->upper = NULL;
(*p_stack)->upper = nw_node;
(*p_stack) = nw_node;
}
//ポップ関数
double pop(double_stack_node** p_stack){
double_stack_node* topNode;
//底のノードをポップしようとしたらエラー終了
if((*p_stack)->lower == NULL){
printf("error : The stack is empty!!\n");
exit(1);
}
double value = (*p_stack)->value;
(*p_stack)->lower->upper = NULL;
topNode = (*p_stack)->lower;
free(*p_stack);
*p_stack = topNode;
return value;
}
スタックをリストを使って実装しました。
今回は入力文字列の長さの最大値が予測できないので、スタックも計算式の項数に応じて伸び縮み出来るようにリストを用いて実装することとしました。
C言語で双方向リストを作る場合は構造体に保持すべき値に加えて、前のノードへのポインタ と 後のノードへのポインタ を含める方法が一般的だと思うので、今回もそうしました。(それ以外があるかどうかは知らないです(´・ω・｀))
計算をする上で一応小数点も扱えるようにするため、項の値はdouble型で保持しています。
スタックについての説明は割愛しますが、実装に当って注意した部分だけ書きます。
1.最低部のノードは次(下)のノードへのポインタをNULLとすることで規定しました。
2.スタックのハンドラはスタックの最上部のノードへのポインタとしました。
もし最低部のノードのポインタをハンドラにするとポップしたりプッシュしたりするたびにリストを全て辿らねばならず無駄が多いからです。
3.プッシュ関数とポップ関数はハンドラへのポインタを介してリストにアクセスするようにしました。
プッシュ操作やポップ操作を行うとスタックの最上部を指し示すポインタの値は変化することになります。この時に最上部を指し示すポインタそのものを利用してスタックにアクセスしていた場合には関数内でプッシュやポップの操作をする前に一つ下のノードのアドレスを記録し、呼び出し元へフィードバックする必要があります。しかしながら、特にポップ関数では変更後の最上部ノードへのポインタを返せません。(ポップした値を返す仕様にする為) そこで、「ハンドラへのポインタ」 つまりスタック最上部へのポインタのポインタ を引数に取ることで直接スタック最上部へのポインタの値を書き換えることにしています。
四則演算の実装
double rnp_calc(const char* input){
double_stack_node* stack = create_stack();
int counter;
int i;
int fEnd = 0;
char* str_operand;
double operand;
double l_operand;
double r_operand;
double result = 0;
for(counter=0;input[counter] != '\0' || fEnd != 1;counter++){
switch(input[counter]){
case '+':
r_operand = pop(&stack);
l_operand = pop(&stack);
result = r_operand + l_operand;
push(&stack,result);
break;
case '-':
r_operand = pop(&stack);
l_operand = pop(&stack);
result = r_operand - l_operand;
push(&stack,result);
break;
case '*':
r_operand = pop(&stack);
l_operand = pop(&stack);
result = r_operand * l_operand;
push(&stack,result);
break;
case '/':
r_operand = pop(&stack);
l_operand = pop(&stack);
result = l_operand / r_operand;
push(&stack,result);
break;
case '=':
result = pop(&stack);
fEnd = 1;
break;
case ' ':
break;
default:
for(i=counter;
input[i] != '+' &&
input[i] != '-' &&
input[i] != '*' &&
input[i] != '/' &&
input[i] != '=' &&
input[i] != ' ' &&
input[i] != '\0';i++){}
if(input[i] != '\0'){
str_operand = malloc(i-counter+1);//文字数+\0分のメモリを確保
strncpy(str_operand,&input[counter],i);
if(str_operand[0]=='~'){
str_operand[0] = '-';
}
operand = atof(str_operand);
counter += i-counter-1;//counterを次の演算子の一つ前に合わせる
free(str_operand);
push(&stack,operand);
}
break;
}
}
return result;
}
えっと…まず煩雑で汚いコードでごめんなさい。他の部分も大概ですが、自分でもこの関数は特に汚くて読みにくいコードだと思っています(´・ω・｀)
汚くて読みにくいので、何をやっているのかざっくりと説明します。
この関数は入力された計算式の文字列を引数で受け取って四則演算をするものです。
処理のイメージとしては、
1. 入力文字列から 1文字読取る
2.読み取った文字列が + – * / = のどれかだったらそれぞれ対応する演算処理を行う。
スペースだったら読み飛ばす。
それ以外の文字列だったら次のスペースまで読み込んでバッファに記録し、double型の数値に変換してスタックに積む。
3. 1 に戻る。
以上の処理を文字列ターミネータ(\0)を読み込むか、 = 演算を行うまで繰り返す。
という流れです。
四則演算の部分ですが、この関数は入力文字列が逆ポーランド記法で記述されていることを前提として期待して書かれているので、演算子を見つけたらスタックの上2つをポップしてその二項を演算することにしています。
= が入力された時にはスタックの最上部にある値をresult変数に記録して、フラグを立ててループを抜けるようにしてあります。= 演算子を処理したかどうかを認識して読み込みを止めないときっと…確実にバグります。
数値を読み込みの部分は、スペース区切りで計算式が入力されることを期待して実装しています(一応数値に続けて演算子が書かれていても何とかなるようには書いていますが)。もし外側のforで数値を読んだ場合には、次のスペースまでの文字数を数えて、strncpy関数を使ってバッファにその項の文字列をコピーしています。あとはバッファの文字列をatof関数でdoubel型の数値に変換してスタックにプッシュして処理を終えます。
この関数では指定された演算子と数値以外の文字が入力された場合のエラー処理を書いていないので必要に応じて書き換えるべきです。恐らく項の文字数を数える時に「次の数値でない文字」までの長さを数えれば良いような気がします。
今回書いた逆ポーランド記法電卓を実現するための関数の説明はざっくりこんなもんです。
きっと沢山のミスデザインと沢山の潜在的実行時エラーを含んでいるので、もし参考にするようなことがあればご注意下さい。こんなゴミコードを参考にするよりご自身で考えた方がきっと良いコードが書けるはずですし…(´・ω・｀)
完動コードへのリンクも一応貼っておきます。
RPNcalc.c (Gists)
ではでは、ノシ~~