Ｃでスタック構造を自作してみた

Ｃ言語でスタック構造（LIFO(Last In First Out) : 後入先出）を自作してみました。
- ##### [やりたいこと](https://github.com/anonymously115/repository115/blob/main/stack.h)
```stack.h
#ifndef STACK_H_
#define STACK_H_

/* スタック構造体 */
typedef struct stack* Stack;

/* コンストラクタ */
Stack newStack(void);

/* スタックに要素を追加する */
void push(Stack, void*);

/* スタックから要素を取り出す */
void* pop(Stack);

#endif /* STACK_H_ */
```
- - -
##### 配列を用いる
（ヘッダファイルに`#define CAPACITY (256)`を追加。数字の部分は任意）
- ###### スタック構造体定義
```stack.c
/* スタック構造 */
struct Stack{
	void* value[CAPACITY];
    size_t size;
};
```
- - -
- ###### コンストラクタ
```c
/*
 * スタックのコンストラクタ
 */
Stack newStack(void){
	//メモリ確保
	Stack stack=(Stack)malloc(sizeof(struct Stack));
	if(!stack){//メモリ確保失敗
		abort();
	}

	//スタックのサイズを0にセットする
	stack->size=0;
	return stack;
}
```
- - -
- ###### スタックに要素を追加
```c
/*
 * スタックの先頭に要素を追加
 * stack : スタック
 * value : 追加するデータ
 */
void push(Stack stack, void* value){
    //データが追加できない場合はエラー
	if(stack->size>=CAPACITY){
		abort();
	}

    //データをセット
    stack->value[stack->size++]=value;
}
```
- - -
- ###### スタックから要素を取り出す
```c
/*
 * スタックから要素を取り出す
 * stack : スタック
 * 返却値 : 取り出すデータ
 */
void* pop(Stack stack){
    if(stack->size){
        return stack->value[--stack->size];
    }else{
        return NULL;
    }
}
```

- - -
##### 自己参照構造体を用いる
- ###### スタック構造体定義
```stack.c
#include <stdlib.h>
#include "stack.h"

/* ノード */
typedef struct node{
	void* value; //データ
	struct node* next; //次のデータの格納位置を示すポインタ
}Node;

/* スタック構造 */
struct stack{
	Node* front; //先頭ノードへのポインタ
};
```
- - -
- ###### コンストラクタ
```c
/*
 * スタックのコンストラクタ
 */
Stack newStack(void){
	//メモリ確保
	Stack stack=(Stack)malloc(sizeof(struct stack));
	if(!stack){//メモリ確保失敗
		abort();
	}

	//スタックの先頭ノードをNULLにセットする
	stack->front=NULL;
	return stack;
}
```
- - -
- ###### スタックに要素を追加
```c
/*
 * スタックの先頭に要素を追加
 * stack : スタック
 * value : 追加するデータ
 */
void push(Stack stack, void* value){
	//メモリ確保
	Node* node=(Node*)malloc(sizeof(Node));
	if(!node){//メモリ確保失敗
		abort();
	}

	//ノードにデータをセット
	node->value=value;

	//新しいノードの次は現在の先頭ノード
	node->next=stack->front;

	//先頭ノードは新しいノード
	stack->front=node;
}
```
- - -
- ###### スタックから要素を取り出す
```c
/*
 * スタックから要素を取り出す
 * stack : スタック
 * 返却値 : 取り出すデータ
 */
void* pop(Stack stack){
	//要素が空ならNULLを返す
	if(!stack->front){
		return NULL;
	}

	//先頭ノードを取得
	Node* node=stack->front;

	//返却値を取得
	void* value=node->value;

	//スタックの先頭を繋ぎ替える
	stack->front=node->next;

	//旧先頭ノードを解放
	free(node);

	//取得した値を返す
	return value;
}
```
- - -
##### サンプルプログラム：[逆ポーランド記法](https://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95)
:::note
今回の仕様は
- 扱う数値：実数、負数も扱う。指数表記(1e+9等)は扱わない。
- 扱う演算子：+(加法), -(減法), "*"(乗法), /(除法), %(剰余), "^"(冪乗)
- これらをコマンドラインに入れて実行する。
- コマンドラインの最後には"="を入れる。
:::
:::note warn
コマンドラインにアスタリスク(*)、ハット(^)を入力するときは、ダブルクォーテーションで囲まなけらばならない。
:::
```rpn.c
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"

/*
 * オペランドを取得する
 * stack : スタック
 * x : (出力)左オペランド
 * y : (出力)右オペランド
 */
void pop2(Stack stack, double* x, double* y){
	//右オペランドを取得する（右オペランドから取り出されることに注意!!）
	double* ptr=(double*)pop(stack);
	if(!ptr)abort();
	*y=*ptr;
	free(ptr);

	//左オペランドを取得する
	ptr=(double*)pop(stack);
	if(!ptr)abort();
	*x=*ptr;
	free(ptr);
}

/*
 * 数値判定
 * 今回は指数表記（1e+9）は扱わない。
 */
bool isNumeric(const char* s){
	const char* c=s;
	if(s[0]=='-'){//マイナスで始まる
		if(strcmp(s,"-")){
			c++;
		}else{//先頭のマイナスのみ
			return false;
		}
	}
	if(s[0]=='+'){//プラスで始まる
		if(strcmp(s,"+")){
			c++;
		}else{//プラスのみ
			return false;
		}
	}

	//小数点（ピリオド）の数
	int p=0;
	while(*c){//文字列末尾までチェック
		if(*c=='.'){//小数点
			if(++p>1){//小数点が2個以上
				//非数値
				return false;
			}
		}else if(!isdigit(*c)){//数字以外の文字が含まれる
			//非数値
			return false;
		}
		c++;
	}
	return true;
}

/*
 * コマンドラインからオペランドと演算子を取得する
 * 扱う数値：実数、負数も扱う。指数表記は扱わない。
 * 扱う演算子：+(加法), -(減法), "*"(乗法), /(除法), %(剰余), "^"(冪乗)
 * コマンドラインの最後は"="
 */
int main(int argc, char* argv[]){
	//スタック初期化
	Stack stack=newStack();

	for(int i=1;i<argc;i++){
		if(!strcmp(argv[i],"=")){//等号
			//スタックから値を取り出す
			double* z=(double*)pop(stack);
			if(z){
				//出力
				printf("%lf\n",*z);
				free(z);
			}else{
				abort();
			}
			//終了
			break;
		}else{
			//メモリ領域確保
			double* ptr=(double*)malloc(sizeof(double));
			if(!ptr){
				abort();
			}

			if(isNumeric(argv[i])){//数値
				//数値をそのまま格納
				*ptr=atof(argv[i]);
			}else{
				double x,y;
				if(!strcmp(argv[i],"+")){//加法
					pop2(stack,&x,&y);
					*ptr=x+y;
				}else if(!strcmp(argv[i],"-")){//減法
					pop2(stack,&x,&y);
					*ptr=x-y;
				}else if(!strcmp(argv[i],"*")){//乗法
					pop2(stack,&x,&y);
					*ptr=x*y;
				}else if(!strcmp(argv[i],"/")){//除法
					pop2(stack,&x,&y);
					if(y){
						*ptr=x/y;
					}else{//ゼロ除算
						abort();
					}
				}else if(!strcmp(argv[i],"%")){//剰余
					pop2(stack,&x,&y);
					if(y){
						*ptr=fmod(x,y);
					}else{//ゼロ除算
						abort();
					}
				}else if(!strcmp(argv[i],"^")){//冪乗
					pop2(stack,&x,&y);
					//(x==0 and y<=0) or (x<0 and yが整数でない) ときには領域エラーが起きる
					*ptr=pow(x,y);
				}else{//数値でも演算子でもない
					free(ptr);
					abort();
				}
			}
			push(stack,(void*)ptr);
		}
	}

	//スタック解放
	free(stack);

	//プログラム終了
	return 0;
}
```