fix: evalexpr & tinyprintf contenaient toute la piscine

10 files changed, 701 insertions, 0 deletions

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 <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#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 <stddef.h>
+
+#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 <ctype.h>
+
+#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 <stddef.h>
+
+#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 <stdio.h>
+#include <stdlib.h>
+
+#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 <stdlib.h>
+
+#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 <stdio.h>
+#include <stdlib.h>
+
+#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 <stdlib.h>
+
+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 */