I made an attempt to translate a math evaluation I had written in C to C. I have faced an issue when I try to loop through the expression and get a segmentation fault.
My tree directory
├── main.c
├── math
│ ├── include.h
│ └── main.c
├── stack
│ ├── include.h
│ └── main.c
My Header and Source File for Stack
//HEADER
#ifndef STACK_H
#define STACK_H
#include <stdio.h>
typedef struct{
int top, max_height;
float data[];
}Stack;
void stack_push(Stack* st, float value);
Stack stack_init(int max);
void stack_replace_top(Stack* st, float value);
void stack_print(Stack* st);
float stack_pop(Stack* st);
int stack_full(Stack* st);
int stack_top(Stack* st);
int stack_height(Stack* st);
int stack_empty(Stack* st);
#endif
//SOURCE
#include <stdio.h>
#include <stdlib.h>
#include "include.h"
int stack_top(Stack* st){return st->top;}
int stack_height(Stack* st){return st->max_height;}
void stack_push(Stack* st, float value){
st->data[st->top] = value;
(st->top) ;
}
float stack_pop(Stack* st){
(st->top)--;
return (st->data[st->top]);
}
Stack stack_init(int max){
return (Stack){0,max};
}
int stack_full(Stack* st){return (st->top >= st->max_height);}
void stack_replace_top(Stack* st, float value){
st->data[st->top - 1] = value;
}
int stack_empty(Stack* st){return (st->top <= 0);}
void stack_print(Stack* st){
int i;
if(st->top == 0){
printf("Stack Is Empty.\n");
}else{
printf("Stack Contents:\n");
for(i=0;i<st->top;i ){
printf("%g\t",st->data[i]);
}
printf("\n\n");
}
}
My Math source, header doesn't have anything important
#include <math.h>
#include <string.h>
#include "include.h"
#include "../stack/include.h"
#include "../utils/include.h"
static float precedence(char op){
switch(op){
case ' ':case '-':return 1;
case '*':case '/':return 2;
case '^':case '%':return 3;
default: return 0;
}
return 0;
}
static float apply_op(float a,float b,char op){
switch(op){
case ' ': return a b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
case '^': return pow(a, b);
case '%': return fmod(a, b);
}
return 0;
}
float evaluate(char* text){
//evaluate a given expression for example (5 5)*7^2
char* token = strtok(text, " ");
//we will use two stacks one for numbers and one for operators
Stack values =stack_init(100);
Stack ops = stack_init(100);
int i=0,size = strlen(token);
printf("Eval: %s\n",token);
printf("4: %c\n",token[4]);
char c;
for(;i<size;i ){
printf("s %d\n",size);
printf("i %d\n",i);
printf("c %c\n",c);
c = token[i];
printf("passed\n");
//if the current character is a number, push it to stack for numbers
switch(c){
case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':{
float val = 0;
//there may be more than one digits in number
while(i < size && c >= '0' && c <= '9'){
val = (val*10) (c - '0');
c = token[i];
i ;
}
//push the number into stack for numbers
stack_push(&values,val);
//as we are also incrementing the i in above while loop we need to decrement it here
i--;
break;
}
case '(':{
//if current character is an opening brace, push it to 'ops'
stack_push(&ops,'(');
break;
}
case ')':{
while(!stack_empty(&ops) && stack_top(&ops) != '('){
float val2 = stack_pop(&values);
float val1 = stack_pop(&values);
char op = stack_pop(&ops);
stack_push(&values,apply_op(val1,val2,op));
}
//pop opening brace
stack_pop(&ops);
break;
}
case ' ': case '-': case '*': case '/': case '^': case '%':{
while(!stack_empty(&ops) && precedence(stack_top(&ops)) >= precedence(c)){
float val2 = stack_pop(&values);
float val1 = stack_pop(&values);
char op = stack_pop(&ops);
stack_push(&values,apply_op(val1,val2,op));
}
//push current operator to 'ops'.
stack_push(&ops,c);
break;
}
}
}
// Entire expression has been parsed at this point, apply remaining ops to remaining values
while(!stack_empty(&ops)){
float val2 = stack_pop(&values);
float val1 = stack_pop(&values);
char op = stack_pop(&ops);
stack_push(&values,apply_op(val1,val2,op));
}
// Top of 'values' contains result, return it
return stack_pop(&values);
}
My mistake appears in the "evaluation" function of the for loop in the math source file. When my loop goes the second time, I get the error. I am really confused because the string the I pass in is "20*2 1" and it is size 6, but when my loop go the second time the index is 4, so it should work. I hope that somebody could help me with my bug.
CodePudding user response：
The problem does not appear to be related to indexing. Instead, your stack implementation is bogus. This ...
typedef struct{ int top, max_height; float data[]; }Stack;
... declares a structure type with a flexible array member. The flexibility involved is that you can make use of the full amount of space allocated for any given instance of the struct, as if its data member were declared with dimension that made it fill as much of that space as possible. That is useful only in conjunction with dynamic memory allocation, which you are not using, and the resulting dynamically-allocated objects cannot usefully be passed or returned by value.
You have two main options:
If you want to stick with the FAM, then
stack_init()must be modified to dynamically allocate large enough instances, and to return a pointer to the allocated result. For example:Stack *stack_init(int max) { Stack *rval = malloc(sizeof(*rval) max * sizeof(rval->data[0])); if (!rval) { abort(); } rval->top = 0; rval->max = max; return rval; }Other changes would be required to accommodate the change of return type, and to free the dynamically allocated stack objects when they were no longer needed.
OR
Change
Stack.datato a pointer, and allocate stack space dynamically . For example:typedef struct { int top, max_height; float *data; } Stack; // ... Stack stack_init(int max) { float *data = malloc(max * sizof(*data)); if (!data && max != 0) { abort(); } return (Stack) { 0, max, data }; }Of course, here again you need to provide for freeing the allocated memory when it is no longer needed.