add: graphs et rushs

1 files changed, 145 insertions, 0 deletions

diff --git a/graphs/piscine/evalexpr/src/evalrpn.c b/graphs/piscine/evalexpr/src/evalrpn.c
new file mode 100644
index 0000000..db493eb
--- /dev/null
+++ b/graphs/piscine/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;
+}