[C] 入力数値が不安定

Question

前提・実現したいこと

逆ポーランド記法で入力された数式の計算を行いたいと考えています。
また、制約としてスタックを用いて実装し、そのスタックは連結リストを用いて実装するというものです。
試作段階としてスタックのみを使用して実装した逆ポーランド記法の計算は問題なく計算できるのですが、スタックを連結リストで実装した際に、入力した数値が小数点以下6位や7位あたりで少しずれてしまい、計算結果が大きく変わってしまいました。数値の変動はGDBで確認しました。
入力方法として逆ポーランド記法の数式を文字列として入力しました。その際、数値と演算子の後にはスペースを入れています。これはスペースまでを一区切りにし、演算子だった場合はその演算子の演算を行い、数値だった場合はatofで数値へ戻しています。

これは、単純にプログラムが間違っているのかC言語やPCの特性なのかそのほかの要因なのか教えていただきたいと考えています。

該当のソースコード

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define STACK_SIZE 8
#define DATA_SIZE 64

struct cell{
    float value;
    struct cell *next;
};

struct cell *head = NULL;
struct cell **p;

bool first_flag = false;

int PostfixNotation(char pnData_c[STACK_SIZE]);
int Push(float data);
int Pop(float *data, int n);
void InsertCell(struct cell **p_pointer, float new_value);
float DeleteCell(struct cell **p_pointer, int n);

int main(){
    char pnData[64];
    float ans = 0;
    int n = 0;
    
    printf("input data(input space after number and operator)\n");
    scanf("%[^\n]%*c", &pnData);
    
    PostfixNotation(pnData);
    
    Pop(&ans, n - 1);
    printf("ans : %.2f\n", ans);
    
    return 0;
}

int PostfixNotation(char pnData_c[STACK_SIZE]){
    char temp[8] = "";
    int i = 0, j = 0, n = 0;
    float pnData_f, first = 0, second = 0;
    while(pnData_c[i] != '\0'){
        if(pnData_c[i] == ' '){
            if(pnData_c[i - 1] == '+'){
                Pop(&second, n - 1);
                n--;
                Pop(&first, n - 1);
                n--;
                Push(first + second);
            }else if(pnData_c[i - 1] == '-'){
                Pop(&second, n - 1);
                n--;
                Pop(&first, n - 1);
                n--;
                Push(first - second);
                n++;
            }else if(pnData_c[i - 1] == '*'){
                Pop(&second, n - 1);
                n--;
                Pop(&first, n - 1);
                n--;
                Push(first * second);
                n++;
            }else if(pnData_c[i - 1] == '/'){
                Pop(&second, n - 1);
                n--;
                Pop(&first, n - 1);
                n--;
                Push(first / second);
                n++;
            }else{
                pnData_f = atof(temp);
                Push(pnData_f);
                n++;
            }
            j = 0;
            i++;
            for(int k = 0; k < STACK_SIZE; k++){
                temp[k] = '\0';
            }
        }
        temp[j] = pnData_c[i];
        j++;
        i++;
    }
}

int Push(float data){
    if(!first_flag){
        p = &head;
        first_flag = true;
    }
    InsertCell(p, data);
    p = &((*p)->next);
    return 1;
}

int Pop(float *data, int i){
    p = &head;
    *data = DeleteCell(p, i - 1);
    return 1;
}

void InsertCell(struct cell **p_pointer, float new_value){
    struct cell* new_cell;
    new_cell = malloc(sizeof(struct cell));
    new_cell->value = new_value;
    new_cell->next = *p_pointer;
    *p_pointer = new_cell;
}

float DeleteCell(struct cell **p_pointer, int i){
    struct cell *delete_cell;
    float pop_data = 0;
    while(i > 0 && *p_pointer != NULL){
        p_pointer = &((*p_pointer)->next);
        i--;
    }
    delete_cell = *p_pointer;
    pop_data = delete_cell->value;
    *p_pointer = delete_cell->next;
    free((void *)delete_cell);
    return pop_data;
}

入力例として
(1.7 + 2.8) * (2.5 - 4.7) + (-1)
を計算する場合は
1.7 2.8 + 2.5 4.7 - * -0.1 +
を入力しています。（最後の+の後にもスペースが入っています）

試作段階のスタックのみを使用したプログラム

#include <stdio.h>
#include <stdlib.h>

#define STACK_SIZE 8

float stack[STACK_SIZE];
int sp = 0;

int Push(float data);
int Pop(float *data);
int PostfixNotation(char pnData_c[STACK_SIZE]);

int main(){
    char pnData[64];
    float ans = 0;
    
    printf("input data(input space after number and operator)\n");
    scanf("%[^\n]%*c", &pnData);
    
    PostfixNotation(pnData);
    
    Pop(&ans);
    printf("ans : %.2f\n", ans);
    
    return 0;
}

int Push(float data){
    if(sp >= STACK_SIZE){
        return 0;
    }else{
        stack[sp] = data;
        sp++;
        return 1;
    }
}

int Pop(float *data){
    if(sp <= 0){
        return 0;
    }else{
        sp--;
        *data = stack[sp];
        return 1;
    }
}

int PostfixNotation(char pnData_c[STACK_SIZE]){
    char temp[8] = "";
    int i = 0, j = 0;
    float pnData_f, first = 0, second = 0;
    while(pnData_c[i] != '\0'){
        if(pnData_c[i] == ' '){
            if(pnData_c[i - 1] == '+'){
                Pop(&second);
                Pop(&first);
                Push(first + second);
            }else if(pnData_c[i - 1] == '-'){
                Pop(&second);
                Pop(&first);
                Push(first - second);
            }else if(pnData_c[i - 1] == '*'){
                Pop(&second);
                Pop(&first);
                Push(first * second);
            }else if(pnData_c[i - 1] == '/'){
                Pop(&second);
                Pop(&first);
                Push(first / second);
            }else{
                pnData_f = atof(temp);
                Push(pnData_f);
            }
            j = 0;
            i++;
            for(int k = 0; k < STACK_SIZE; k++){
                temp[k] = '\0';
            }
        }
        temp[j] = pnData_c[i];
        j++;
        i++;
    }
}

Answer 1

ええと、根本的な原因は、連結リスト版でスタックの実装をミスっていることです。
「1 2 - 」とか「1 2 / 」とかを試してみれば分かりますが、LIFO(FILO)が実現できていません。

連結リストを使ったスタックは、提示されているコードよりももっと単純に書けます。

Push: headに新たな値を持ったセルを挿入する(現在のheadのセルがnextになる)。
Pop: headのセルの値を取り出し、そのセルを削除する(nextのセルがheadになる)。

これだけです。連結リスト内を走査する必要はありません。

Comments

[DreamTheater]

横から失礼します。
float型見て安易に丸め誤差と回答した自分が恥ずかしいです。
コードをちゃんと読まないとダメですね。

[Gurt]

スタックのpush,popはそのように実装することができるのですね。
確かに詳しく調べてみると計算の順序が関係ない加算乗算はできていましたが、減算除算ができていませんでした。
参考にした教本では、pushは配列にただ追加して配列の番号をポインタのようにpopで参照するというものでした。
そのため連結リストの挿入と削除においてイメージの差異が生まれたのだと思います。
もう一度やり直してみます。
完全に解決したらBAにさせていただきます。

[Gurt]

すみません、お待たせいたしました。
無事に解決できました。

Answer 2

float使っているので浮動小数点の丸め誤差が発生したのでは？
doubleにすれば少し精度が高くなりますが、、、

以下をご覧ください
FLP02-C. 精度の高い計算が必要な場合は浮動小数点数の使用を避ける
C言語 計算の誤差

Comments

[Gurt]

連結リストを使う前はたまたまfloatでも計算できていたということなのですかね・・・
doubleにしても計算結果変わらずでした。
ただ、GDBでみた数値はfloatよりはブレ幅が小さいように感じました。
他に何か要因があるのでしょうか・・・