2014 Data Structures and Algorithms


コードを次のように変更してみよう。
  1. 教科書の339ページから340ページに書いてある変更を加えてみよう。
#include <stdio.h>
#include <stdlib.h>
 
typedef struct tagBUNSUU {
    int bunbo;      /* 分母 */
    int bunsi;      /* 分子 */
} BUNSUU;
 
BUNSUU stack_array[10];
 
/*スタックの上限は10 */
int stack_top = 0;
 
void stack_push(BUNSUU *value) {
    /* スタックにBUNSUUをプッシュする */
    if(stack_top!=10) {
        stack_array[stack_top].bunbo = value->bunbo;
        stack_array[stack_top].bunsi = value->bunsi;
        stack_top++;
    } else {
        printf("スタックオーバフローです。数字が多すぎます\n");
        exit(EXIT_FAILURE);
    }
}
 
void stack_pop(BUNSUU *ret) {
    /* スタックからBUNSUUをとってくる */
    stack_top--;
    if(stack_top >= 0) {
        ret->bunbo = stack_array[stack_top].bunbo;
        ret->bunsi = stack_array[stack_top].bunsi;
        return;
    } else {
        printf("スタックアンダフローです。"
                            "演算子の場所が違います\n");
        exit(EXIT_FAILURE);
    }
}
 
int main(void) {
    char line[256];
    int c;
    BUNSUU st1, st2;
 
    printf("逆ポーランド記法で数式を入力してください:");
    scanf("%s", line);
 
    c = 0;
    while(line[c] != '\0') {
        if(line[c] >= '0' && line[c] <= '9') {
            /* 数字だった場合は,
               その数字をそのままスタックに入れる */
            st1.bunbo = 1;
            st1.bunsi = line[c] - '0';
            stack_push(&st1);
        } else {
            /* 数字でなかった場合は,
               スタックの上2つの数字をとってきて演算する */
            stack_pop(&st1);
            stack_pop(&st2);
            if(line[c] == '+') {
                st2.bunsi =
                        st2.bunsi * st1.bunbo + st1.bunsi * st2.bunbo;
                st2.bunbo = st1.bunbo * st2.bunbo;
                stack_push(&st2);
            } else if(line[c] == '-') {
                st2.bunsi =
                        st2.bunsi * st1.bunbo - st1.bunsi * st2.bunbo;
                st2.bunbo = st1.bunbo * st2.bunbo;
                stack_push(&st2);
            } else if(line[c] == '*') {
                st2.bunsi = st2.bunsi * st1.bunsi;
                st2.bunbo = st1.bunbo * st2.bunbo;
                stack_push(&st2);
            } else if(line[c] == '/') {
                st2.bunsi = st2.bunsi * st1.bunbo;
                st2.bunbo = st2.bunbo * st1.bunsi;
                if(st2.bunbo == 0) {
                    printf("0で除算しました\n");
                    exit(EXIT_FAILURE);
                }
                stack_push(&st2);
            } else {
                printf("無効な文字が入っています\n");
                exit(EXIT_FAILURE);
            }
        }
        c++;
    }
    stack_pop(&st1);
    if(stack_top != 0) {
        /* スタックに数字がまだ残っている場合 */
        printf("正しくない数式です。数字が多すぎます\n");
        exit(EXIT_FAILURE);
    }
    printf("解は%lfです\n", (double)st1.bunsi / (double)st1.bunbo);
 
    return EXIT_SUCCESS;
}



#include <stdio.h>
#include <stdlib.h>
 
/* 与えられた数 */
char number[] = "1234";
char created_num[8];
 
void make_rpn(int num,int exp) {
    static int isused[4] = {0, 0, 0, 0};
    /* RPNを作成する再帰関数 */
    int i;
 
    if(num + exp == 7) {
        /* 全体で7文字であれば表示 */
        created_num[7] = '\0';
        printf("%s\n", created_num);
        return;
    } else {
        if(num - exp >= 2) {
            /* 数字が演算子より2つ以上多ければ,
               演算子を入れてもよい */
            created_num[num + exp] = '+';
            make_rpn(num, exp + 1);
            created_num[num + exp] = '-';
            make_rpn(num, exp + 1);
            created_num[num + exp] = '*';
            make_rpn(num, exp + 1);
            created_num[num + exp] = '/';
            make_rpn(num, exp + 1);
        }
        if(num <= 3) {
            /* 数が3つ以下であれば,数を入れてもよい */
            for(i = 0; i < 4; i++) {
                if(isused[i] == 0) {
                    isused[i] = 1;
                    created_num[num + exp] = number[i];
                    make_rpn(num + 1,exp);
                    isused[i] = 0;
                }
            }
        }
    }
}
 
int main(void) {
    make_rpn(0, 0);
    return EXIT_SUCCESS;
}



コードを次のように変更してみよう。
  1. 教科書の345ページに書いてある変更を加えてみよう。
#include <stdio.h>
#include <stdlib.h>
 
/* make_numによって作られた4つの数字 */
char created_num[5];
 
/* make_rpnによって作られたrpn */
char created_rpn[8];
 
/* solveに使われる仮想分数構造体 */
typedef struct tagBUNSUU {
    int bunbo;      /* 分母 */
    int bunsi;      /* 分子 */
} BUNSUU;
BUNSUU stack_array[4];
 
/*スタックの上限は4 */
int stack_top = 0;
 
void stack_push(BUNSUU *value) {
    /* スタックにBUNSUUをプッシュする */
    stack_array[stack_top].bunbo = value->bunbo;
    stack_array[stack_top].bunsi = value->bunsi;
    stack_top++;
}
 
void stack_pop(BUNSUU *ret) {
    /* スタックからBUNSUUをとってくる */
    stack_top--;
    ret->bunbo = stack_array[stack_top].bunbo;
    ret->bunsi = stack_array[stack_top].bunsi;
    return;
}
 
int solve(void) {
    int c;
    BUNSUU st1, st2;
 
    stack_top = 0;
    c = 0;
    while(created_rpn[c] != '\0') {
        if(created_rpn[c] >= '0' && created_rpn[c] <= '9') {
            /* 数字だった場合は,
               その数字をそのままスタックに入れる */
            st1.bunbo = 1;
            st1.bunsi = created_rpn[c] - '0';
            stack_push(&st1);
        } else {
            /* 数字でなかった場合は,
               スタックの上2つの数字をとってきて演算する */
            stack_pop(&st1);
            stack_pop(&st2);
            if(created_rpn[c] == '+') {
                st2.bunsi =
                        st2.bunsi * st1.bunbo + st1.bunsi * st2.bunbo;
                st2.bunbo = st1.bunbo * st2.bunbo;
                stack_push(&st2);
            } else if(created_rpn[c] == '-') {
                st2.bunsi =
                        st2.bunsi * st1.bunbo - st1.bunsi * st2.bunbo;
                st2.bunbo=st1.bunbo*st2.bunbo;
                stack_push(&st2);
            } else if(created_rpn[c] == '*') {
                st2.bunsi = st2.bunsi * st1.bunsi;
                st2.bunbo = st1.bunbo * st2.bunbo;
                stack_push(&st2);
            } else if(created_rpn[c] == '/') {
                st2.bunsi = st2.bunsi * st1.bunbo;
                st2.bunbo = st2.bunbo * st1.bunsi;
                if(st2.bunbo == 0) {
                    /* 0で割り算してしまった場合は失敗 */
                    return 0;
                }
                stack_push(&st2);
            }
        }
        c++;
    }
    stack_pop(&st1);
 
    if(st1.bunbo * 10 == st1.bunsi) {
        return 1;
    }
 
    return 0;
}
 
int make_rpn(int num,int exp) {
    /* RPNを作成する再帰関数 */
    static int isused[4] = {0, 0, 0, 0};
    int i;
 
    if(num + exp == 7) {
        created_rpn[7] = '\0';
        // printf("%s\n",created_rpn);
        /* 全体で7文字であれば,それを計算 */
        if(solve()) {
            return 1;
            /* 計算結果が10になれば,それ以後の再帰を止める */
        }
        return 0;
    } else {
        if(num - exp >= 2) {
            /* 数字が演算子より2つ以上多ければ,
               演算子を入れてもよい */
            created_rpn[num + exp] = '+';
            if(make_rpn(num, exp + 1)) {
                return 1;
            }
            created_rpn[num + exp] = '-';
            if(make_rpn(num, exp + 1)) {
                return 1;
            }
            created_rpn[num + exp] = '*';
            if(make_rpn(num, exp + 1)) {
                return 1;
            }
            created_rpn[num + exp] = '/';
            if(make_rpn(num, exp + 1)) {
               return 1;
            }
        }
        if(num <= 3) {
            /* 数が3つ以下であれば,数を入れてもよい */
            for(i = 0; i < 4; i++) {
                if(isused[i] == 0) {
                    isused[i] = 1;
                    created_rpn[num + exp] = created_num[i];
                    if(make_rpn(num + 1, exp)) {
                        isused[i] = 0;
                        return 1;
                    }
                    isused[i] = 0;
                }
            }
        }
    }
    return 0;
}
 
void make_num(int keta, int num) {
    /* 数の組み合わせを作る再帰関数 */
    int i;
    if(keta == 4) {
        created_num[4] = '\0';
        /* 数が4桁になったらRPNを作成する */
        if(make_rpn(0, 0)) {
            printf("%s:%s\n", created_num, created_rpn);
        } else {
            printf("%s:解けません\n", created_num);
        }
        return;
    }
    for(i = num; i <= 9; i++) {
        created_num[keta] = i + '0';
        make_num(keta + 1, i);
    }
}
 
int main(void) {
    make_num(0, 0);
    return EXIT_SUCCESS;
}