add: graphs et rushs

1 files changed, 199 insertions, 0 deletions

diff --git a/rushs/tinyprintf/evalexpr/src/shunting_yard.c b/rushs/tinyprintf/evalexpr/src/shunting_yard.c
new file mode 100644
index 0000000..2db5fc8
--- /dev/null
+++ b/rushs/tinyprintf/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;
+}