basic_cal.png

/**
* By utilizing a doubly linked list...
*/
typedef struct NodeStruct {
    int val;
    struct NodeStruct *next;
    struct NodeStruct *pre;
}*Node;

Node NodeCreate(int val) {
    Node x = (Node)malloc(sizeof(*x));
    x->val = val;
    x->next = x->pre = NULL;
    return x;
}

typedef struct {
    int count;
    Node head, tail;
}*Queue;

Queue QueueCreate() {
    Queue queue = (Queue)malloc(sizeof(*queue));
    queue->head = queue->tail = NULL;
    queue->count = 0;
    return queue;
}

void QueueEnqueue(Queue queue, int val) {
    Node x = NodeCreate(val);
    if (queue->count == 0) {
        queue->head = queue->tail = x;
    } else {
        x->pre = queue->head;
        queue->head->next = x;
        queue->head = x;
    }
    queue->count++;
}

int QueueDequeue(Queue queue) {
    Node tail = queue->tail;
    int val = tail->val;
    queue->tail = tail->next;
    queue->count--;
    free(tail);
    return val;
}

void QueuePush(Queue queue, int val) {
    Node x = NodeCreate(val);
    if (queue->count == 0) {
        queue->head = queue->tail = x;
    } else {
        x->next = queue->tail;
        queue->tail->pre = x;
        queue->tail = x;
    }
    queue->count++;
}

int QueuePop(Queue queue) {
    Node head = queue->head;
    int val = head->val;
    queue->head = head->pre;
    queue->count--;
    free(head);
    return val;
}

bool QueueIsEmpty(Queue queue) { return queue->count == 0; }

int parse_val(char *s, size_t n, size_t *start) {
    int val = 0;
    while (*start < n && !isdigit(s[*start])) { (*start)++; }
    while (*start < n && isdigit(s[*start])) { val = 10 * val + (s[(*start)++] - '0'); }
    return val;
}

int perform(int val1, int val2, char op) {
    if (op == '-') { return val1 - val2; }
    if (op == '+') { return val1 + val2; }
    if (op == '*') { return val1 * val2; }
    if (op == '/') { return val1 / val2; }
    return 0;
}

int calculate(char * s) {
    Queue ops = QueueCreate(), vals = QueueCreate();
    size_t i = 0, n = strlen(s);
    while (i < n) {
        if (isdigit(s[i])) {
            QueueEnqueue(vals, parse_val(s, n, &i));
        } else if (s[i] == ' ') {
            I++;
        } else {
            char op = s[I];
            if (op == '*' || op == '/') {
                QueueEnqueue(vals, perform(QueuePop(vals), parse_val(s, n, &i), op));
            } else {
                QueueEnqueue(ops, op);
                I++;
            }
        }
    }
    while (!QueueIsEmpty(ops)) { 
        int val1 = QueueDequeue(vals), val2 = QueueDequeue(vals);
        QueuePush(vals, perform(val1, val2, QueueDequeue(ops))); 
    }
    return QueueDequeue(vals);
}