DS_project4: eval

DS_project4.md

DS Project4

Syntax:

./eval options "expression"

Input:

The input expression can be an infix expression or postfix expression after read in the expression.

Options:

-e : evaluate the input expression and print out the result value. The input expression is a postfix expression or an infix expression.

-t : transform the input expression into a postfix expression and print out the postfix expression.

---

Example commands:

./eval -e "10+20*3"
will output 70 (input expression is an infix expression)

./eval -e "10 20 3 * +"
will output 70 (input expression is a postfix expression)

./eval -e "10 20 * 3 +"
will output 203 (input expression is a postfix expression)

./eval -t "A*B+C"
will output AB*C+

main.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <ctype.h>
#include <string.h>

#include "vector.h"

bool is_operand(const char* s, int len) {
    if (len == 0)
        len = strlen(s);

    for (int i=0; i<len; i++)
        if (isdigit(s[i]) == false && isalpha(s[i]) == false)
            return false;

    return true;
}

bool is_str_alpha(const char* s) {
    int len = strlen(s);

    for (int i=0; i<len; i++)
        if (isalpha(s[i]) == false)
            return false;

    return true;
}

bool is_operator(const char* s) {
    char operators[] = "+-*/()";
    for (int i=0; i<sizeof(operators)/sizeof(char); i++)
        if (s[0] == operators[i])
            return true;
    return false;
}

int priority(const char* s) {
    if (s[0] == '+' || s[0] == '-')
        return 1;
    if (s[0] == '*' || s[0] == '/')
        return 2;

    return 0;
}

bool check(Vector* tokens) {
    int len = vector_length(tokens);

    // parethesis
    int cnt = 0;
    for (int i=0; i<len; i++) {
        char* token = (char*) vector_at(tokens, i);
        if (strcmp(token, "(") == 0)
            cnt++;
        else if (strcmp(token, ")") == 0)
            cnt--;

        free(token);
    }
    if (cnt != 0)
        return false;

    // check token
    for (int i=0; i<len; i++) {
        char* token = (char*) vector_at(tokens, i);
        if (is_operator(token) == false && is_operand(token, 0) == false)
            return false;
        free(token);
    }

    // check constutive operators
    for (int i=0; i<len-1; i++) {
        char* item = (char*) vector_at(tokens, i);
        char* next = (char*) vector_at(tokens, i+1);

        if (strstr("+-*/", item) != NULL && strstr("+-*/", next) != NULL) {
            free(item);
            free(next);
            return false;
        }
    }

    return true;
}

Vector* infix_to_postfix(Vector* tokens) {
    Vector* output = new_vector(sizeof(char*));
    Vector* stack = new_vector(sizeof(char*));

    for (int i=0; i<vector_length(tokens); i++) {
        char* token = (char*) vector_at(tokens, i);

        if (strcmp(token, "(") == 0) {
            vector_push_back(stack, token);
        }
        else if (strcmp(token, ")") == 0) {
            char* top = (char*) vector_at(stack, -1);
            while (strcmp(top, "(") != 0) {
                vector_push_back(output, top);

                if (vector_length(stack) < 1) {
                    free_vector(output);
                    free_vector(stack);
                    free(token);
                    free(top);
                    return NULL;
                }
                vector_pop_back(stack);

                top = (char*) vector_at(stack, -1);
            }

            if (vector_length(stack) < 1) {
                free_vector(output);
                free_vector(stack);
                free(token);
                free(top);
                return NULL;
            }
            vector_pop_back(stack);

            free(top);
        }
        else if (is_operator(token)) {
            char* top = (char*) vector_at(stack, -1);
            while (vector_length(stack) > 0 && priority(top) >= priority(token)){
                vector_push_back(output, top);

                if (vector_length(stack) < 1) {
                    free_vector(output);
                    free_vector(stack);
                    free(token);
                    free(top);
                    return NULL;
                }
                vector_pop_back(stack);

                top = (char*) vector_at(stack, -1);
            }

            vector_push_back(stack, token);

            free(top);
        }
        else if (is_operand(token, 0)) {
            vector_push_back(output, token);
        }

        free(token);
    }

    while (vector_length(stack) > 0) {
        char* top = (char*) vector_pop_back(stack);
        vector_push_back(output, top);
        free(top);
    }

    free_vector(stack);
    return output;
}

bool is_computable(Vector* tokens) {
    for (int i=0; i<vector_length(tokens); i++) {
        char* item = (char*) vector_at(tokens, i);
        if (is_operand(item, strlen(item)) && is_str_alpha(item)) {
            free(item);
            return false;
        }
        free(item);
    }

    return true;
}

Vector* unary_to_binary(Vector* tokens) {
    Vector* result = new_vector(sizeof(char*));
    char* front = (char*) vector_at(tokens, 0);
    vector_push_back(result, front);
    free(front);

    for (int i=1; i<vector_length(tokens); i++) {
        char* item = (char*) vector_at(tokens, i);
        char* prev = (char*) vector_at(tokens, i-1);

        if (strstr("+-", item) != NULL && strcmp(prev, "(") == 0) {
            vector_push_back(result, "0");
            vector_push_back(result, item);
        }
        else {
            vector_push_back(result, item);
        }

        free(item);
        free(prev);
    }

    return result;
}

char* eval_postfix(Vector* tokens, bool iscomputable) {
    if (iscomputable == false) {
        int len = 0;
        for (int i=0; i<vector_length(tokens); i++) {
            char* item = (char*) vector_at(tokens, i);
            len += strlen(item);
            len += 1;
            free(item);
        }

        char* result = (char*) malloc (sizeof(char)* len);
        result[len-1] = '\0';
        int idx = 0;
        for (int i=0; i<vector_length(tokens); i++) {
            if (i != 0) {
                result[idx] = ' ';
                idx++;
            }

            char* item = (char*) vector_at(tokens, i);
            strcpy(result + idx, item);
            idx += strlen(item);

            free(item);
        }

        return result;
    }

    Vector* stack = new_vector(sizeof(double));
    for (int i=0; i<vector_length(tokens); i++) {
        char* item = (char*) vector_at(tokens, i);

        if (is_operand(item, strlen(item))) {
            double* value = (double*) malloc (sizeof(double));
            *value = atof(item);
            vector_push_back(stack, value);
            free(value);
        }
        else {
            if (vector_length(stack) < 2) {
                free_vector(stack);
                free(item);

                return NULL;
            }

            double* d2 = (double*) vector_pop_back(stack);
            double* d1 = (double*) vector_pop_back(stack);

            if (strcmp(item, "+") == 0) {
                double* result = (double*) malloc (sizeof(double));
                *result = *d1 + *d2;
                vector_push_back(stack, result);
                free(result);
            }
            else if (strcmp(item, "-") == 0) {
                double* result = (double*) malloc (sizeof(double));
                *result = *d1 - *d2;
                vector_push_back(stack, result);
                free(result);
            }
            else if (strcmp(item, "*") == 0) {
                double* result = (double*) malloc (sizeof(double));
                *result = *d1 * *d2;
                vector_push_back(stack, result);
                free(result);
            }
            else if (strcmp(item, "/") == 0) {
                if (*d2 == 0) {
                    free(d1);
                    free(d2);
                    free(item);
                    free_vector(stack);

                    return NULL;
                }

                double* result = (double*) malloc (sizeof(double));
                *result = *d1 / *d2;
                vector_push_back(stack, result);
                free(result);
            }
            else {
                free(d1);
                free(d2);
                free(item);
                free_vector(stack);

                return NULL;
            }

            free(d1);
            free(d2);
        }

        free(item);
    }

    if (vector_length(stack) != 1) {
        free_vector(stack);
        return NULL;
    }

    char* answer = (char*) malloc (sizeof(char) * 256);
    double* value = vector_at(stack, 0);
    sprintf(answer, "%f", *value);

    free(value);
    free_vector(stack);

    return answer;
}

Vector* get_tokens_from_infix(const char* s) {
    Vector* tokens = new_vector(sizeof(char*));

    int start = 0;
    const int len = strlen(s);
    while (start < len) {
        int end = start;

        if (is_operand(s + end, 1)) {
            while (end < len && is_operand(s + end, 1))
                end++;

            int substr_len = end - start;
            char* substr = (char*) malloc (sizeof(char) * (substr_len+1));
            substr[substr_len] = '\0';
            strncpy(substr, s+start, substr_len);

            vector_push_back(tokens, substr);

            start = end;
        }
        else if (is_operator(s+end)) {
            char* substr = (char*) malloc (sizeof(char) * 2);
            substr[1] = '\0';
            strncpy(substr, s+start, 1);

            vector_push_back(tokens, substr);

            start = end+1;
        }
        else {
            free_vector(tokens);
            return NULL;
        }
    }

    return tokens;
}

Vector* get_tokens_from_postfix(const char* s) {
    Vector* tokens = new_vector(sizeof(char*));

    int start = 0;
    int len = strlen(s);

    while (start < len) {
        int end = start;

        while (end < len && (is_operator(s+end) || is_operand(s+end, 1)))
            end++;

        if (s[end] == ' ' || s[end] == '\0') {
            int substr_len = end - start;
            char* substr = (char*) malloc(sizeof(char) * substr_len);
            substr[substr_len-1] = '\0';
            strncpy(substr, s+start, substr_len);

            vector_push_back(tokens, substr);

            start = end+1;
        }
        else {
            free_vector(tokens);
            return NULL;
        }
    }

    return tokens;
}

int main(int argc, char* argv[]) {
    if (argc <= 2)
        return 0;

    char* input = argv[2];

    bool space_exist = false;
    for (int i=0; i<strlen(input); i++) {
        if (input[i] == ' ') {
            space_exist = true;
            break;
        }
    }

    Vector* tokens = NULL;
    Vector* postfix = NULL;
    Vector* fixed = NULL;
    char* answer = NULL;

    if (space_exist) {
        postfix = get_tokens_from_postfix(input);
    }
    else {
        tokens = get_tokens_from_infix(input);
        if (tokens == NULL) {
            free_vector(tokens);
            free_vector(postfix);
            free_vector(fixed);
            free(answer);

            printf("Illegal Expression\n");
            return 0;
        }

        if (check(tokens) == false) {
            free_vector(tokens);
            free_vector(postfix);
            free_vector(fixed);
            free(answer);

            printf("Illegal Expression\n");
            return 0;
        }

        fixed = unary_to_binary(tokens);
        postfix = infix_to_postfix(fixed);
    }

    if (postfix == NULL) {
        free_vector(tokens);
        free_vector(postfix);
        free_vector(fixed);
        free(answer);

        printf("Illegal Expression\n");
        return 0;
    }

    int operator_cnt = 0;
    int operand_cnt = 0;

    for (int i=0; i<vector_length(postfix); i++) {
        char* item = (char*) vector_at(postfix, i);
        if (is_operator(item))
            operator_cnt++;
        else if (is_operand(item, strlen(item)))
            operand_cnt++;
        free(item);
    }

    if (operator_cnt+1 != operand_cnt) {
        free_vector(tokens);
        free_vector(postfix);
        free_vector(fixed);
        free(answer);

        printf("Illegal Expression\n");
        return 0;
    }

    bool computable = false;
    if (strcmp(argv[1], "-e") == 0)
        computable = is_computable(postfix);

    answer = eval_postfix(postfix, computable);
    if (answer == NULL) {
        free_vector(tokens);
        free_vector(postfix);
        free_vector(fixed);
        free(answer);

        printf("Illegal Expression\n");
        return 0;
    }

    printf("%s\n", answer);

    free_vector(tokens);
    free_vector(postfix);
    free_vector(fixed);
    free(answer);

    /*    Vector* postfix = get_tokens_from_postfix(input);
        if (vector_length(postfix) != 1 && postfix != NULL) {
        bool computable = false;
        if (strcmp(argv[1], "-e") == 0)
        computable = is_computable(postfix);

        char* answer = eval_postfix(postfix, computable);
        printf("%s\n", answer);
        if (answer != NULL)
        printf("%s\n", answer);
        else
        printf("Illegal Expression\n");

        free(answer);
        free_vector(postfix);
        return 0;
        }

        Vector* infix = get_tokens_from_infix(input);
        if (infix != NULL) {
        Vector* fixed = unary_to_binary(infix);
        postfix = infix_to_postfix(fixed);

        if (postfix != NULL) {
        bool computable = false;
        if (strcmp(argv[1], "-e") == 0)
        computable = is_computable(postfix);

        char* answer = eval_postfix(postfix, computable);
        if (answer != NULL)
        printf("%s\n", answer);
        else
        printf("Illegal Expression\n");

        free(answer);
        free_vector(fixed);
        free_vector(postfix);
        free_vector(infix);
        return 0;
        }

        printf("Illegal Expression\n");
        free_vector(fixed);
        free_vector(infix);
        }

        printf("Illegal Expression\n");
        */

    return 0;
}

Makefile

vector.o:
    clang -std=c99 -c vector.c

main.o: vector.h
    clang -std=c99 -c main.c

eval: main.o vector.o
    clang -std=c99 -o eval main.o vector.o

all: eval

clean:
    rm -f *.o
    rm -f eval

vector.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#include "vector.h"

Vector* new_vector(int data_size) {
    Vector* v = (Vector*) malloc (sizeof(Vector));
    v->data_size = data_size;
    v->length = 0;
    v->capacity = 10;

    v->data = (void*) malloc (data_size * v->capacity);

    return v;
}

void free_vector(Vector* v) {
    if (v == NULL) return;

    v->data = NULL;
    free(v->data);
    v = NULL;
    free(v);
}

int vector_length(const Vector* v) {
    return v->length;
}

void vector_resize(Vector* v, int new_size) {
    if (new_size <= v->capacity) return;

    v->capacity = new_size;
    v->data = (void*) realloc(v->data, v->data_size * v->capacity);
}

bool vector_insert(Vector* v, int idx, void* item) {
    if (idx < 0)
        idx = v->length + idx;

    if (idx >= v->length)
        return false;

    if (v->length + 1 >= v->capacity) {
        vector_resize(v, v->capacity*2);
    }

    const int size = v->data_size;

    for (int i=v->length; i>idx; i--) {
        memcpy(v->data + (i * size), v->data + ((i-1) * size), size);
    }

    memcpy(v->data + (idx * size), item, size);
    v->length++;

    return true;
}

void* vector_remove(Vector* v, int idx) {
    if (idx < 0)
        idx = v->length + idx;

    if (idx >= v->length)
        return NULL;

    const int size = v->data_size;
    void* temp = malloc(size);
    memcpy(temp, v->data + (idx*size), size);

    for (int i=idx; i<v->length-1; i++) {
        memcpy(v->data + (i * size), v->data + ((i+1) * size), size);
    }

    v->length--;

    return temp;
}



bool vector_assign(Vector* v, int idx, void* item) {
    if (idx < 0)
        idx = v->length + idx;

    if (idx >= v->length)
        return false;

    memcpy(v->data + (idx * v->data_size), item, v->data_size);
    return true;
}

void* vector_at(const Vector* v, int idx) {
    if (idx < 0)
        idx = v->length + idx;

    if (idx >= v->length)
        return NULL;

    void* temp = malloc(v->data_size);
    memcpy(temp, v->data + (idx*v->data_size), v->data_size);
    return temp;
}

void vector_push_back(Vector* v, void* item) {
    if (v->length >= v->capacity) {
        vector_resize(v, v->capacity*2);
    }

    memcpy(v->data + (v->length * v->data_size), item, v->data_size);
    v->length++;
}

void* vector_pop_back(Vector *v) {
    if (v->length == 0)
        return NULL;

    void* temp = malloc (v->data_size);
    memcpy(temp, v->data + ((v->length-1) * v->data_size), v->data_size);
    v->length--;

    return temp;
}

vector.h

#include <stdbool.h>

typedef struct
{
    int data_size;
    int length;
    int capacity;

    void* data;
} Vector;

Vector* new_vector(int data_size);
void free_vector(Vector* v);

int vector_length(const Vector* v);

void vector_resize(Vector* v, int new_size);

bool vector_insert(Vector* v, int idx, void* item);
void* vector_remove(Vector* v, int idx);

bool vector_assign(Vector* v, int idx, void* item);
void* vector_at(const Vector* v, int idx);

void vector_push_back(Vector* v, void* item);
void* vector_pop_back(Vector* v);