NITMic Advent Calendar 2021 16日目の記事です。
大学の授業の自由課題でC言語のプログラムを組むことになったので作りました。
以下GitHubのリポジトリのリンクです
環境
gcc version 9.3.0
-
実行環境
- WSL2
- Ubuntu 20.04 LTS
環境構築に関してはネットで山のように記事が転がってるので割愛します。
インストールガイド
純度100%のC言語なのでgccとgitさえあればcloneだけで動かせます。
インストールしたいディレクトリで、
$ git clone https://github.com/suzshiro1024/Calculator.git
とすればひとまずOKです。
対応する演算
四則演算と()を用いた優先順位の変更に対応しています。
なお、計算結果が負数になることは許容されます(例:3-4)が、計算式に負数が入ることには対応していません(例:-4+3)。
また、小数点以下の計算にも対応していません。このため、割り算の結果が小数になる場合は小数点以下は切り捨てになります(例:4/3 = 1)。
実行方法
インストールしたディレクトリで
$ gcc stack.c -c
$ gcc parse.c -c
$ gcc calc.c -c
$ gcc main.c -c
$ gcc -o 任意の実行ファイル名 stack.o parse.o calc.o main.o
を順番に行う。
- ファイルを使う場合
src/calc.txtを作成し、その中に計算式を記入してから
$ ./任意の実行ファイル名
とするとcalc.txtの中身に計算結果が書き足されます。
- ファイルを使わない場合 そのまま上記のコマンドを実行すると
>
と表示されるので、計算式を入力すると答えが返ってきます。
実装解説
この電卓は大まかに次の2つのフェーズに分かれています。
1. 入力された計算式を逆ポーランド記法に書き換える
2. 逆ポーランド記法になった数式を計算し、結果を返す
逆ポーランド記法って何さ
逆ポーランド記法は一般的な数式の記法と異なり、被演算子(数字)の後に演算子が来る記法です。
例えば3 + 4は3 4 +と記述されます。
逆ポーランド記法の計算式は簡単に計算できるアルゴリズムがあるので、そちらが使えるように入力された式を逆ポーランド記法に翻訳します。
スタックを実装する
スタックって何さ
食堂のお盆のように上にどんどん積んでいって、取り出すのは上からという抽象データ構造です。
最後に積んだものを最初に取れるという形式でこれをLIFOと呼んだりします。
スタックをどこで使うか
第1フェーズ、第2フェーズの双方の根幹を担っています。詳細は後述します。
スタックの実装方針
単方向連結リストを使って、ポインタのつなぎ合わせで考えます。
まずはこのnodeを作ります。このような中に複数のデータを抱えたかたまりを作るのに最適な方法として構造体というものが存在します。今回はこれを使って実装してみます。
typedef struct node{
char data; //ノードの中身
struct node* next_node; //次のノードへのポインタ
} node;
nodeの中に入れるデータは文字型1文字とします。
今後node単位で扱う機会が多いのでtypedefで型名を与えて使いやすくしておきます。
さて、スタックでは先頭をうまく取り扱う必要があります。なぜなら先ほども述べた通りスタックはLIFOであり、新しいデータは先頭に入れるし、中から取り出すデータは先頭のデータと決まっているからです。そこで、スタックの先頭にいるnodeをポインタで管理します。
node* sp; //スタックのtopを指すポインタ(先頭のノードを指す)
スタックへの操作
スタックでは以下の操作を実装します。
- is_empty : スタックの中にデータがあるかどうか確認する
- push : スタックの先頭にデータを追加する
- pop : スタックの先頭のデータを取り出す
- peek : スタックの先頭のデータを閲覧する
- stack_size : スタックの中にいるデータの数を数える
順番に見ていきます
is_empty
is_emptyではスタックの中がカラであるかどうかを確認します。先ほど言った通りスタックの先頭を指すポインタspがいるので、これがNULLであるかどうかで簡単にわかります。
bool is_empty(){
return sp == NULL; //もしスタックのtopを指すポインタの中身がNULLであるならばスタックは空
}
push
pushではスタックにデータを追加しています。大まかな動きは以下の通りです。
1. まずnode_newを作る
2. データを代入する
3. スタックの先頭を今作ったnode_newに変更する
4. もし、スタックの中にすでにデータがあれば今迄の先頭のnodeをnode_newのnext_nodeに登録する
まわりくどい書き方ですがとりあえずコードを見ればなんとなくわかると思います。
void push(char data){
node* node_new; // 新しいノードを指すポインタを用意する
//メモリ領域の確保
node_new = (node*)malloc(sizeof(node));
//メモリ領域の確保に失敗した場合はここでtrueとなってエラーを出して終了
if(node_new == NULL){
puts("ERROR malloc Failed");
exit(1);
}
//新しいノードへの中身の代入(ポインタの先の構造体なのでアロー演算子->を用いた間接参照を利用)
node_new->data = data;
//スタックがカラだったかそうでないかで条件分岐する
if(is_empty()){
//スタックがカラだった場合、スタックのtopを今作ったノードとし、次のノードは存在しないのでポインタの先はNULLにしておく
sp = node_new;
node_new->next_node = NULL;
}else{
//スタックがカラでなかった場合、スタックのtopは今作ったノードに置き換える。そのあと、今作ったノードの次のノードに今までtopだったノードを置く
node* tmp = sp;
sp = node_new;
node_new->next_node = tmp;
}
}
引数に文字1文字を取り、新しいnodeを作りスタックの状態を確認して代入していきます。本当に最初に書いた手順をそのまま書き起こしただけなのですぐに理解できると思います。
pop
popではpushと逆にデータを取り出していきます。大まかな動きは以下の通りです。
1. スタックがカラかどうか確認し、カラならNULLを返す
2. 先頭のnodeのデータを引っ張り出す
3. spを付け替える
4. 引っ張り出したデータを返す
こちらもさっさとコードを出してしまいます。
char pop(){
//スタックがカラの場合NULLを返す
if(is_empty()){
return NULL;
}
//スタックのtopをpopする
node* node_pop = sp; //popするノードを指すポインタ
char data = node_pop->data; //データを返り値用の変数に格納
sp = node_pop->next_node; //topをpopするノードの次のノードに変更
free(node_pop); //今popしたノードが確保していたメモリ領域はもう必要ないので解放
return data;
}
peek
peekでは先頭のデータを参照します。popと違いスタックから取り出してしまわず、あくまで先頭のデータを見るだけです。
char peek(){
//スタックがカラの場合NULLを返す
if(is_empty()){
return NULL;
}
//スタックのtopを返す。スタック自体は変化しない
node* node_peek = sp; //peekするノードを指すポインタ
char data = node_peek->data;//データを返り値用の変数に格納
return data;
}
stack_size
stack_sizeはスタックのサイズを数えます。単純にspから1つずつnodeをたどり数を数えて返します。
int stack_size(){
node* pointer = sp;
if(pointer == NULL){
printf("ERROR: Stack is not exist.\n");
exit(1);
}
int size = 1;
while(pointer->next_node != NULL){
size++;
pointer = pointer->next_node;
}
}
ソースコードの全体像
#include <stdbool.h>
#include <stdlib.h>
//ノード構造体の定義
typedef struct node{
char data; //ノードの中身
struct node *next_node; //次のノードへのポインタ
} node;
node *sp; //スタックのtopを指すポインタ(先頭のノードを指す)
//関数のプロトタイプ宣言
bool is_empty(void);
void push(char value);
char pop(void);
char peek(void);
int stack_size(void);
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include "stack.h"
//スタックがカラかどうか確認する関数
bool is_empty(){
return sp == NULL; //もしスタックのtopを指すポインタの中身がNULLであるならばスタックは空
}
//push
void push(char data){
node* node_new; // 新しいノードを指すポインタを用意する
//メモリ領域の確保
node_new = (node*)malloc(sizeof(node));
//メモリ領域の確保に失敗した場合はここでtrueとなってエラーを出して終了
if(node_new == NULL){
puts("ERROR malloc Failed");
exit(1);
}
//新しいノードへの中身の代入(ポインタの先の構造体なのでアロー演算子->を用いた間接参照を利用)
node_new->data = data;
//スタックがカラだったかそうでないかで条件分岐する
if(is_empty()){
//スタックがカラだった場合、スタックのtopを今作ったノードとし、次のノードは存在しないのでポインタの先はNULLにしておく
sp = node_new;
node_new->next_node = NULL;
}else{
//スタックがカラでなかった場合、スタックのtopは今作ったノードに置き換える。そのあと、今作ったノードの次のノードに今までtopだったノードを置く
node* tmp = sp;
sp = node_new;
node_new->next_node = tmp;
}
}
//pop
char pop(){
//スタックがカラの場合NULLを返す
if(is_empty()){
return NULL;
}
//スタックのtopをpopする
node* node_pop = sp; //popするノードを指すポインタ
char data = node_pop->data; //データを返り値用の変数に格納
sp = node_pop->next_node; //topをpopするノードの次のノードに変更
free(node_pop); //今popしたノードが確保していたメモリ領域はもう必要ないので解放
return data;
}
//スタックの最上位の中身を参照する関数
char peek(){
//スタックがカラの場合NULLを返す
if(is_empty()){
return NULL;
}
//スタックのtopを返す。スタック自体は変化しない
node* node_peek = sp; //peekするノードを指すポインタ
char data = node_peek->data;//データを返り値用の変数に格納
return data;
}
//スタックのノードの数を数える関数
int stack_size(){
node* pointer = sp;
if(pointer == NULL){
printf("ERROR: Stack is not exist.\n");
exit(1);
}
int size = 1;
while(pointer->next_node != NULL){
size++;
pointer = pointer->next_node;
}
}
インストールガイドの説明でお察しの通り分割コンパイルをする関係でプロトタイプ宣言を行います。そのあたりはヘッダに分割しています。
逆ポーランド変換アルゴリズムを実装する
実装するのはこんな感じのアルゴリズムです
与えられた文字列から1文字ずつ読み込んで、ふるいにかけてい行きます。
1. 数字である場合 : バッファにそのまま書き込みます
2. ')'である場合 : スタックから'('が出てくるまでpopし続け、バッファに書き込みます
3. '('である場合 : スタックにpushします
ここまでに該当しない場合、読み込んだ文字が演算子(+,-,*,/)のいずれかであることが確定します。
演算子の処理は以下の通りです。
- スタックがカラである場合 : 演算子をスタックに追加
- スタックの先頭の演算子と読み込んだ演算子の優先度を比較して、読み込んだ演算子の優先度のほうが低い : スタックから演算子をpopしてバッファへ書き込みます。その後またスタックがカラか確認するフェーズへ戻ります。
- 2.で読み込んだ演算子のほうが優先順位が高い : 読み込んだ演算子をスタックにpushします
ここでいう優先度は *,/ > +/- > (,)です。
このアルゴリズムを実装したものが以下のコードになります。
//演算子の優先順位を決定する定数
#define FIRST 1
#define SECOND 2
#define THIRD 3
//関数のプロトタイプ宣言
int rank(char operator);
char* parse(char str[], int length);
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include "parse.h"
#include "stack.h"
//演算記号の優先順位を決定する関数
int rank(char operator){
if(operator == '*' || operator == '/'){
//'*','/'は優先順位1を与える
return FIRST;
}else if(operator == '+' || operator == '-'){
//'+','-'は優先順位2を与える
return SECOND;
}else{
//その他は優先順位3を与える
return THIRD;
}
}
//中値記法を逆ポーランド記法に変換するアルゴリズム
char* parse(char str[], int length){
char token; //スタックからpopした文字
//返り値となる文字列を格納するバッファ
char* buffer = calloc(length+1, sizeof(char));
//NULLチェック
if(buffer == NULL){
puts("ERROR calloc Failed");
exit(1);
}
int indexbuf = 0;
for(int i = 0; i < length; i++){
if(isdigit(str[i])){
//ヘッダの先が文字が数字であるならばそのままバッファに格納
buffer[indexbuf++] = str[i];
if(!isdigit(str[i+1])){
/*
もしヘッダの一つ先の文字が数字でないならば、区別のために空白を挿入
空白を用いることで並ぶ数字を見分けることが可能
*/
buffer[indexbuf++] = ' ';
}
}else if(str[i] == ')'){
/*
'('までスタックをpopし、バッファへ送る
条件は スタックがカラでない && '('に到達した
*/
while((token = pop()) != NULL && token != '('){
buffer[indexbuf++] = token;
}
if(token == NULL){
puts("ERROR: '(' is missing");
exit(1);
}
}else if(str[i] == '('){
//'('が来たらスタックにpush
push(str[i]);
}else if(peek() == NULL){
/*
スタックのtopがNULL => スタックがカラならヘッダの先の文字をスタックに格納
ここに来るまでに数字,'(',')'の3種類は消えているので、ここで格納されるのは演算記号のみ
*/
push(str[i]);
}else{
while(peek() != NULL){
if(rank(str[i]) > rank(peek())){
//スタックのtopの演算子の優先順位がヘッダの先の演算子の優先順位より低い場合
buffer[indexbuf++] = pop();
}else{
//逆の場合
push(str[i]);
break;
}
}
if(peek() == NULL){
push(str[i]);
}
}
}
while((token = pop()) != NULL){
buffer[indexbuf++] = token;
}
buffer[indexbuf++] = NULL;
return buffer;
}
当たり前ですが引数には文字列を取り、返り値も文字列です。
for文を使って引数の文字列を1文字ずつ調べ、上記の処理を行います。
逆ポーランド記法の計算式を計算する
先ほど逆ポーランド記法のアルゴリズムの実装は非常に簡単と話しましたが、それはあくまで他言語での話で、C言語での実装には少々苦労する部分があります。
それがC言語では文字列を扱うのが非常に難しいという点です。javaのようなString型が存在しないC言語では文字列はchar型の配列として実現されますがこれが非常に話をややこしくしています。
実際にこのプログラムを作成しているときもこの問題の処理にかなり時間がかかりました。
一旦この問題を解決した部分だけ見てもらおうと思います。
//数字の桁数を計算
int cal_digit(int num){
int digit = 0;
//値が負数ならカウントを増やす("-"の分)
if(num < 0){
digit++;
}
do{
num /= 10;
digit++;
}while(num != 0);
return digit;
}
//文字列の数字を逆順pushする関数
int num_push(char* buffer,int i){
int count = 0;
int index = i;
//区切り用の空白をpush
if(peek() != ' '){
push(' ');
}
//負数かどうか確認
if(buffer[i]=='-'){
i++;
count++;
}
//桁数のカウントを行う
while(isdigit(buffer[i++])){
count++;
}
//index+桁数-1で数字の1の位が格納されているindexになる
for(int j = index + count - 1; j >= index; j--){
push(buffer[j]);
}
//ヘッダの位置を動かし、pushした数字の部分を飛ばさせる
return index + count;
}
//文字列の数字をpopする関数
int num_pop(){
//数字を格納
char* num = calloc(stack_size()+1,sizeof(char));
//NULLチェック
if(num == NULL){
puts("ERROR calloc Failed");
exit(1);
}
//数字をバッファに取り出し
int index = 0;
if(!isdigit(peek())&&peek()!='-'){
//空白を取り除く
char tmp = pop();
}
while(isdigit(peek()) || peek() == '-'){
num[index] = pop();
index++;
}
//文字列を数字に置換
int return_num = atoi(num);
//メモリ領域を解放
free(num);
return return_num;
}
とても面倒くさいことをやっていますが、簡単に説明すると
"-123"という数字が来たら、"3"→"2"→"1"→"-"という順番に一気にpushさせています。
さらにスタックの中でどこまでが一つの数字かわかるように、数字をスタックにpushする前に空白を挟むようにしています。
また、関数で数字をまとめて処理している都合上、あとからどこまでをスタックにpushしたかがわからないと関数を出た後にすでにpushした数字をまた読んでしまいバグるので、何文字目までを処理したか返り値として返しています。
popはその逆で、数字を一気に取り出して整数型に変換しその値を返しています。
それでは計算部の方に移りましょう。逆ポーランド記法の計算式を計算するアルゴリズムはよく知られており、説明不要かと思われるのでコードだけ書いておきます。
int calc(char* buffer,int length){
char token; //スタックからpopした文字
int indexbuf = 0;
for(int i = 0; i < length; i++){
if(isdigit(buffer[i])){
//数字が出てきたら数字をpushする関数を呼び出し(2桁以上の数を1の位から逆順にpushする必要があるため)
//ヘッダの位置を動かし、pushした数字の部分を飛ばさせる
i = num_push(buffer,i);
}else{
//演算子が出てきた場合はスタックから数字二つを呼び出してatoiして計算を行う。終わったらそれを文字列に変えて再び格納
int num1 = num_pop();
int num2 = num_pop();
//結果を格納する数字
int num = 0;
//演算部
if(buffer[i]=='+'){
num = num2+num1;
}else if(buffer[i]=='-'){
num = num2-num1;
}else if(buffer[i]=='*'){
num = num2*num1;
}else if(buffer[i]=='/'){
num = num2/num1;
}
//結果の数字の桁数を計算
int digit = cal_digit(num);
//桁数分の文字列を確保
char* push_num = calloc(digit+2,sizeof(char));
//数字を文字列に置換
int n = snprintf(push_num,digit+2,"%d",num);
if(n < 0){
printf("ERROR: Overflow");
exit(1);
}
//数字をnum_pushで逆順push
//返り値は破棄するので適当な変数に格納しておく
int tmp = num_push(push_num,0);
free(push_num);
}
}
int result = num_pop();
free(buffer);
return result;
}
C言語の仕様に振り回されてはいますが
- 数字が来たらスタックにpush
- 演算子が来たらスタックから数字を2つpopして演算して結果をスタックにpush
という一般的なアルゴリズムです。
ソースコードの全体像
//関数のプロトタイプ宣言
int cal_digit(int num);
int num_push(char* buffer, int i);
int num_pop(void);
int calc(char* buffer, int length);
#include <stdio.h>
#include <ctype.h>
#include "stack.h"
#include "parse.h"
#include "calc.h"
//数字の桁数を計算
int cal_digit(int num){
int digit = 0;
//値が負数ならカウントを増やす("-"の分)
if(num < 0){
digit++;
}
do{
num /= 10;
digit++;
}while(num != 0);
return digit;
}
//文字列の数字を逆順pushする関数
int num_push(char* buffer,int i){
int count = 0;
int index = i;
//区切り用の空白をpush
if(peek() != ' '){
push(' ');
}
//負数かどうか確認
if(buffer[i]=='-'){
i++;
count++;
}
//桁数のカウントを行う
while(isdigit(buffer[i++])){
count++;
}
//index+桁数-1で数字の1の位が格納されているindexになる
for(int j = index + count - 1; j >= index; j--){
push(buffer[j]);
}
//ヘッダの位置を動かし、pushした数字の部分を飛ばさせる
return index + count;
}
//文字列の数字をpopする関数
int num_pop(){
//数字を格納
char* num = calloc(stack_size()+1,sizeof(char));
//NULLチェック
if(num == NULL){
puts("ERROR calloc Failed");
exit(1);
}
//数字をバッファに取り出し
int index = 0;
if(!isdigit(peek())&&peek()!='-'){
//空白を取り除く
char tmp = pop();
}
while(isdigit(peek()) || peek() == '-'){
num[index] = pop();
index++;
}
//文字列を数字に置換
int return_num = atoi(num);
//メモリ領域を解放
free(num);
return return_num;
}
//構文解析と計算
int calc(char* buffer,int length){
char token; //スタックからpopした文字
int indexbuf = 0;
for(int i = 0; i < length; i++){
if(isdigit(buffer[i])){
//数字が出てきたら数字をpushする関数を呼び出し(2桁以上の数を1の位から逆順にpushする必要があるため)
//ヘッダの位置を動かし、pushした数字の部分を飛ばさせる
i = num_push(buffer,i);
}else{
//演算子が出てきた場合はスタックから数字二つを呼び出してatoiして計算を行う。終わったらそれを文字列に変えて再び格納
int num1 = num_pop();
int num2 = num_pop();
//結果を格納する数字
int num = 0;
//演算部
if(buffer[i]=='+'){
num = num2+num1;
}else if(buffer[i]=='-'){
num = num2-num1;
}else if(buffer[i]=='*'){
num = num2*num1;
}else if(buffer[i]=='/'){
num = num2/num1;
}
//結果の数字の桁数を計算
int digit = cal_digit(num);
//桁数分の文字列を確保
char* push_num = calloc(digit+2,sizeof(char));
//数字を文字列に置換
int n = snprintf(push_num,digit+2,"%d",num);
if(n < 0){
printf("ERROR: Overflow");
exit(1);
}
//数字をnum_pushで逆順push
//返り値は破棄するので適当な変数に格納しておく
int tmp = num_push(push_num,0);
free(push_num);
}
}
int result = num_pop();
free(buffer);
return result;
}
main関数の実装
ここに関しては基本的に自由だと思います。一応参考程度に見てください。
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include "stack.h"
#include "parse.h"
#include "calc.h"
#define STR_LENGTH 128
int main(void){
char str[STR_LENGTH];
FILE* fp;
fp = fopen("calc.txt","r");
if(fp == NULL){
printf(" > ");
scanf("%s",str);
}else{
fscanf(fp,"%s",str);
}
fclose(fp);
char* buffer = parse(str, sizeof(str)/sizeof(char*));
//逆ポーランド記法になった文字列バッファの長さを取得
int length = strlen(buffer);
//計算させる
int result = calc(buffer, length);
fp = fopen("calc.txt","a");
if(fp==NULL){
puts("ERROR File Not Found");
printf("result = %d",result);
}else{
fprintf(fp,"=%d\n",result);
}
}
終わりに
ここまで読んでくれてありがとうございます。
今後の課題
この電卓にはいくつか課題が残されています
-4とか書くだけで動かなくなってしまう点
これはparserの方を改善する必要がありそうです。ですが演算子の-と数字についた-の見分けがつかないのが
かなり事態をややこしくしそうです。1個前が演算子なら数字にくっついてるとみなす。とかやればいけるかな？
小数点演算に対応していない
こちらはparser,calc双方の改善が必要な予感...
更新
- 12/20 : バグの修正を反映