From 73c2b00a10c5786ddeeacc915e233fd4df1c9321 Mon Sep 17 00:00:00 2001 From: Martial Simon Date: Sat, 11 Oct 2025 22:19:00 +0200 Subject: fix: evalexpr & tinyprintf contenaient toute la piscine --- rushs/evalexpr/src/evalexpr.c | 93 +++++++++++++++ rushs/evalexpr/src/evalexpr.h | 43 +++++++ rushs/evalexpr/src/evalrpn.c | 145 +++++++++++++++++++++++ rushs/evalexpr/src/fifo.h | 29 +++++ rushs/evalexpr/src/fifo_access.c | 61 ++++++++++ rushs/evalexpr/src/fifo_setup_destroy.c | 44 +++++++ rushs/evalexpr/src/shunting_yard.c | 199 ++++++++++++++++++++++++++++++++ rushs/evalexpr/src/stack.c | 57 +++++++++ rushs/evalexpr/src/stack.h | 20 ++++ rushs/evalexpr/src/stack_struct.h | 10 ++ 10 files changed, 701 insertions(+) create mode 100644 rushs/evalexpr/src/evalexpr.c create mode 100644 rushs/evalexpr/src/evalexpr.h create mode 100644 rushs/evalexpr/src/evalrpn.c create mode 100644 rushs/evalexpr/src/fifo.h create mode 100644 rushs/evalexpr/src/fifo_access.c create mode 100644 rushs/evalexpr/src/fifo_setup_destroy.c create mode 100644 rushs/evalexpr/src/shunting_yard.c create mode 100644 rushs/evalexpr/src/stack.c create mode 100644 rushs/evalexpr/src/stack.h create mode 100644 rushs/evalexpr/src/stack_struct.h (limited to 'rushs/evalexpr/src') diff --git a/rushs/evalexpr/src/evalexpr.c b/rushs/evalexpr/src/evalexpr.c new file mode 100644 index 0000000..5012355 --- /dev/null +++ b/rushs/evalexpr/src/evalexpr.c @@ -0,0 +1,93 @@ +#include "evalexpr.h" + +#include +#include +#include + +#define BUFFER_SIZE 10 + +char *get_input(void) +{ + size_t r; + char buf[BUFFER_SIZE]; + size_t size = 0; + char *expr = malloc(size * sizeof(char) + 1); + if (expr == NULL) + return NULL; + expr[0] = '\0'; + do + { + r = fread(buf, sizeof(char), BUFFER_SIZE - 1, stdin); + if (r != 0) + { + buf[r] = '\0'; + size += r; + char *tmp = realloc(expr, size * sizeof(char) + 1); + if (tmp == NULL) + { + free(expr); + return NULL; + } + expr = tmp; + strcat(expr, buf); + } + } while (r != 0); + if (size == 0) + { + free(expr); + return NULL; + } + if (expr[size - 1] == '\n') + expr[size - 1] = '\0'; + return expr; +} + +void cleanup(char *expr, char *rpn) +{ + free(expr); + free(rpn); +} + +int main(int argc, char **argv) +{ + if ((argc == 2 && strcmp(argv[1], "-rpn") != 0) || (argc > 2)) + return 4; + char *expr = get_input(); + if (expr == NULL) + return 4; + if (argc == 1) + { + char *rpn; + int e = shunting_yard(expr, &rpn); + if (e != 0) + return e; + // call shunting yard + int retval; + e = evalrpn(rpn, &retval); + if (e != 0) + { + cleanup(expr, rpn); + return e; + } + // FREE RPN + printf("%d\n", retval); + cleanup(expr, rpn); + // return + return 0; + } + + if (argc == 2 && strcmp(argv[1], "-rpn") == 0) + { + // call rpn eval + int retval; + int e = evalrpn(expr, &retval); + printf("%d\n", retval); + // return + free(expr); + if (e != 0) + return e; + return 0; + } + + return 4; +} diff --git a/rushs/evalexpr/src/evalexpr.h b/rushs/evalexpr/src/evalexpr.h new file mode 100644 index 0000000..d440ae1 --- /dev/null +++ b/rushs/evalexpr/src/evalexpr.h @@ -0,0 +1,43 @@ +#ifndef EVALEXPR_H +#define EVALEXPR_H + +#include + +#include "fifo.h" +#include "stack.h" +#include "stack_struct.h" + +enum token_type +{ + NUMBER = 0, + SUB = 1, + ADD = 1, + MOD = 2, + DIV = 2, + MUL = 2, + EXP = 3, + UN_PLUS = 4, + UN_MINUS = 4, + PAR_LEFT = 5, + PAR_RIGHT = 5, + WRONG_TOKEN = -1, +}; + +struct token +{ + enum token_type type; + int value; +}; + +// evalrpn +int parse_number(const char *expr, size_t *offset); +int get_operands(struct stack **s, int *op1, int *op2); +int my_pow(int a, int b); +int evalrpn(const char *expr, int *retval); + +// shunting yard +int opcmp(struct token *op1, struct token *op2); +enum token_type get_type(char op); +int shunting_yard(const char *expr, char **rpn); + +#endif /* ! EVALEXPR_H */ diff --git a/rushs/evalexpr/src/evalrpn.c b/rushs/evalexpr/src/evalrpn.c new file mode 100644 index 0000000..db493eb --- /dev/null +++ b/rushs/evalexpr/src/evalrpn.c @@ -0,0 +1,145 @@ +#include + +#include "evalexpr.h" + +int parse_number(const char *expr, size_t *offset) +{ + for (*offset = 0; + expr[*offset] && expr[*offset] >= '0' && expr[*offset] <= '9'; + (*offset)++) + { + continue; + } + (*offset)--; + + int res = 0; + int pow = 1; + for (size_t n = 0; n <= *offset; n++, pow *= 10) + { + res += (expr[*offset - n] - '0') * pow; + } + + return res; +} + +int get_operands(struct stack **s, int *op1, int *op2) +{ + if (*s == NULL) + { + return 2; + } + *op1 = stack_peek(*s); + *s = stack_pop(*s); + if (*s == NULL) + { + return 2; + } + *op2 = stack_peek(*s); + *s = stack_pop(*s); + return 0; +} + +// Computes a to the bth +int my_pow(int a, int b) +{ + if (b == 0) + { + return 1; + } + if (a == 0) + { + return 0; + } + + int res = 1; + int c = b / 2; + while (c != 0) + { + res *= a * a; + c /= 2; + } + if (b % 2 != 0) + res *= a; + return res; +} + +int dispatch(const char c, struct stack **s, int op1, int op2) +{ + switch (c) + { + case '*': + *s = stack_push(*s, op1 * op2); + break; + case '+': + *s = stack_push(*s, op1 + op2); + break; + case '-': + *s = stack_push(*s, op2 - op1); + break; + case '/': + if (op1 == 0) + { + return 3; + } + *s = stack_push(*s, op2 / op1); + break; + case '%': + if (op1 == 0) + { + return 3; + } + *s = stack_push(*s, op2 % op1); + break; + case '^': + if (op1 < 0) + { + return 3; + } + *s = stack_push(*s, my_pow(op2, op1)); + break; + default: + return 1; + } + return 0; +} + +int evalrpn(const char *expr, int *retval) +{ + struct stack *s = NULL; + + for (size_t i = 0; expr[i]; i++) + { + if (expr[i] >= '0' && expr[i] <= '9') + { + size_t offset; + int val = parse_number(expr + i, &offset); + s = stack_push(s, val); + i += offset; + } + else if (isspace(expr[i])) + continue; + else + { + int op1; + int op2; + if (get_operands(&s, &op1, &op2) == 2) + { + return 2; + } + + int d = dispatch(expr[i], &s, op1, op2); + if (d != 0) + { + return d; + } + } + } + + if (s == NULL) + { + return 0; + } + *retval = stack_peek(s); + s = stack_pop(s); + return (!s) ? 0 : 2; +} diff --git a/rushs/evalexpr/src/fifo.h b/rushs/evalexpr/src/fifo.h new file mode 100644 index 0000000..b330eac --- /dev/null +++ b/rushs/evalexpr/src/fifo.h @@ -0,0 +1,29 @@ +#ifndef FIFO_H +#define FIFO_H + +#include + +#include "evalexpr.h" + +struct list +{ + struct token *data; + struct list *next; +}; + +struct fifo +{ + struct list *head; + struct list *tail; + size_t size; +}; + +struct fifo *fifo_init(void); +size_t fifo_size(struct fifo *fifo); +void fifo_push(struct fifo *fifo, struct token *elt); +struct token *fifo_head(struct fifo *fifo); +void fifo_pop(struct fifo *fifo); +void fifo_clear(struct fifo *fifo); +void fifo_destroy(struct fifo *fifo); + +#endif /* !FIFO_H */ diff --git a/rushs/evalexpr/src/fifo_access.c b/rushs/evalexpr/src/fifo_access.c new file mode 100644 index 0000000..1986a09 --- /dev/null +++ b/rushs/evalexpr/src/fifo_access.c @@ -0,0 +1,61 @@ +#include +#include + +#include "fifo.h" + +size_t fifo_size(struct fifo *fifo) +{ + return fifo->size; +} + +void fifo_push(struct fifo *fifo, struct token *elt) +{ + struct list *new = malloc(sizeof(struct list)); + if (new == NULL) + { + return; + } + new->data = elt; + + if (fifo_size(fifo) == 0) + { + fifo->head = new; + } + new->next = NULL; + if (fifo_size(fifo) != 0) + { + fifo->tail->next = new; + } + fifo->tail = new; + + fifo->size++; +} + +struct token *fifo_head(struct fifo *fifo) +{ + return fifo->head->data; +} + +void fifo_pop(struct fifo *fifo) +{ + if (fifo_size(fifo) == 0) + { + return; + } + if (fifo_size(fifo) == 1) + { + free(fifo->head->data); + free(fifo->head); + fifo->head = NULL; + fifo->tail = NULL; + fifo->size = 0; + return; + } + + struct list *tmp = fifo->head->next; + free(fifo->head->data); + free(fifo->head); + fifo->head = tmp; + + fifo->size--; +} diff --git a/rushs/evalexpr/src/fifo_setup_destroy.c b/rushs/evalexpr/src/fifo_setup_destroy.c new file mode 100644 index 0000000..0f99ad0 --- /dev/null +++ b/rushs/evalexpr/src/fifo_setup_destroy.c @@ -0,0 +1,44 @@ +#include + +#include "fifo.h" + +struct fifo *fifo_init(void) +{ + struct fifo *f = malloc(sizeof(struct fifo)); + if (f == NULL) + { + return NULL; + } + + f->size = 0; + f->head = NULL; + f->tail = NULL; + + return f; +} + +void fifo_clear(struct fifo *fifo) +{ + for (struct list *l = fifo->head; l != fifo->tail;) + { + struct list *tmp = l->next; + free(l->data); + free(l); + l = tmp; + } + if (fifo->tail) + { + free(fifo->tail->data); + free(fifo->tail); + } + + fifo->head = NULL; + fifo->tail = NULL; + fifo->size = 0; +} + +void fifo_destroy(struct fifo *fifo) +{ + fifo_clear(fifo); + free(fifo); +} diff --git a/rushs/evalexpr/src/shunting_yard.c b/rushs/evalexpr/src/shunting_yard.c new file mode 100644 index 0000000..2db5fc8 --- /dev/null +++ b/rushs/evalexpr/src/shunting_yard.c @@ -0,0 +1,199 @@ +#include +#include + +#include "evalexpr.h" + +enum assoc +{ + NONE, + RIGHT, + LEFT, +}; + +int opcmp(struct token *op1, struct token *op2) +{ + return op1->type - op2->type; +} + +enum assoc get_assoc(struct token *op) +{ + if (op->type == EXP) + { + return RIGHT; + } + return LEFT; +} + +enum token_type get_type(char op) +{ + switch (op) + { + case '*': + return MUL; + case '/': + return DIV; + case '-': + return SUB; + case '+': + return ADD; + case '%': + return MOD; + case '^': + return EXP; + case '(': + return PAR_LEFT; + case ')': + return PAR_RIGHT; + default: + return WRONG_TOKEN; + } +} + +char *fifo_to_expr(struct fifo *output, size_t size_offset) +{ + char *res = malloc((2 * fifo_size(output) + size_offset) * sizeof(char)); + if (!res) + { + fifo_destroy(output); + return NULL; + } + res[2 * fifo_size(output) + size_offset - 1] = '\0'; + size_t i = 0; + while (fifo_size(output) > 0) + { + if (fifo_head(output)->type == NUMBER) + { + i += sprintf(res + i, "%d", fifo_head(output)->value) - 1; + } + else + { + res[i] = fifo_head(output)->value; + } + fifo_pop(output); + i++; + if (fifo_size(output) != 0) + { + res[i] = ' '; + i++; + } + } + fifo_destroy(output); + return res; +} + +int handle_rpar(struct tstack **opstack, struct fifo *output, struct token **t) +{ + while (*opstack) + { + struct token *o2 = tstack_peek(*opstack); + if (o2->value == '(') + { + free(o2); + break; + } + *opstack = tstack_pop(*opstack); + fifo_push(output, o2); + } + if (*opstack == NULL) + { + free(*t); + fifo_destroy(output); + return 2; + } + free(*t); + *opstack = tstack_pop(*opstack); + return 0; +} + +int empty_opstack(struct tstack **opstack, struct fifo *output) +{ + while (*opstack) + { + struct token *t = tstack_peek(*opstack); + if (t->value == '(' || t->value == ')') + { + fifo_destroy(output); + return 1; + } + *opstack = tstack_pop(*opstack); + fifo_push(output, t); + } + return 0; +} + +void pop_ops(struct tstack **opstack, struct fifo *output, struct token *t) +{ + while (*opstack) + { + struct token *o2 = tstack_peek(*opstack); + if (!(o2->value != '(' + && (opcmp(t, o2) < 0 + || (opcmp(t, o2) == 0 && get_assoc(t) == LEFT)))) + { + break; + } + + *opstack = tstack_pop(*opstack); + fifo_push(output, o2); + } +} + +void handle_numbers(struct fifo *output, size_t *i, int *size_offset, + const char *expr) +{ + size_t offset; + int val = parse_number(expr + *i, &offset); + struct token *t = malloc(sizeof(struct token)); + t->type = NUMBER; + t->value = val; + fifo_push(output, t); + *i += offset; + *size_offset += offset; +} + +int shunting_yard(const char *expr, char **rpn) +{ + struct fifo *output = fifo_init(); + struct tstack *opstack = NULL; + int size_offset = 0; + for (size_t i = 0; expr[i]; i++) + { + if (expr[i] >= '0' && expr[i] <= '9') + { + handle_numbers(output, &i, &size_offset, expr); + } + else if (expr[i] != ' ') + { + struct token *t = malloc(sizeof(struct token)); + t->value = expr[i]; + if ((t->type = get_type(expr[i])) == WRONG_TOKEN) + { + free(t); + return 1; + } + if (t->value == '(') + { + opstack = tstack_push(opstack, t); + continue; + } + else if (t->value == ')') + { + if (handle_rpar(&opstack, output, &t) != 0) + return 2; + continue; + } + pop_ops(&opstack, output, t); + opstack = tstack_push(opstack, t); + } + } + + if (empty_opstack(&opstack, output) != 0) + { + return 1; + } + *rpn = fifo_to_expr(output, size_offset); + if (!*rpn) + return 4; + + return 0; +} diff --git a/rushs/evalexpr/src/stack.c b/rushs/evalexpr/src/stack.c new file mode 100644 index 0000000..14f659e --- /dev/null +++ b/rushs/evalexpr/src/stack.c @@ -0,0 +1,57 @@ +#include "stack.h" + +#include + +struct stack *stack_push(struct stack *s, int e) +{ + struct stack *new = malloc(sizeof(struct stack)); + new->data = e; + new->next = NULL; + + new->next = s; + return new; +} + +struct stack *stack_pop(struct stack *s) +{ + if (s == NULL) + { + return NULL; + } + + struct stack *res = s->next; + free(s); + return res; +} + +int stack_peek(struct stack *s) +{ + return s->data; +} + +struct tstack *tstack_push(struct tstack *s, struct token *e) +{ + struct tstack *new = malloc(sizeof(struct tstack)); + new->token = e; + new->next = NULL; + + new->next = s; + return new; +} + +struct tstack *tstack_pop(struct tstack *s) +{ + if (s == NULL) + { + return NULL; + } + + struct tstack *res = s->next; + free(s); + return res; +} + +struct token *tstack_peek(struct tstack *s) +{ + return s->token; +} diff --git a/rushs/evalexpr/src/stack.h b/rushs/evalexpr/src/stack.h new file mode 100644 index 0000000..d08e465 --- /dev/null +++ b/rushs/evalexpr/src/stack.h @@ -0,0 +1,20 @@ +#ifndef STACK_H +#define STACK_H + +#include "evalexpr.h" +#include "stack_struct.h" + +struct tstack +{ + struct token *token; + struct tstack *next; +}; + +struct stack *stack_push(struct stack *s, int e); +struct stack *stack_pop(struct stack *s); +int stack_peek(struct stack *s); + +struct tstack *tstack_push(struct tstack *s, struct token *e); +struct tstack *tstack_pop(struct tstack *s); +struct token *tstack_peek(struct tstack *s); +#endif /* !STACK_H */ diff --git a/rushs/evalexpr/src/stack_struct.h b/rushs/evalexpr/src/stack_struct.h new file mode 100644 index 0000000..105cd5d --- /dev/null +++ b/rushs/evalexpr/src/stack_struct.h @@ -0,0 +1,10 @@ +#ifndef STACK_STRUCT_H +#define STACK_STRUCT_H + +struct stack +{ + int data; + struct stack *next; +}; + +#endif /* ! STACK_STRUCT_H */ -- cgit v1.2.3