C Solution with Stack...it's fast cuz it's C...


  • 0
    T
    struct node{
        long int val;
        struct node* next;
    };
    
    struct Stack{
        struct node* top;
    };
    typedef struct node* node;
    typedef struct Stack* Stack;
    
    Stack New(){
        Stack result = malloc(sizeof(struct Stack));
        result->top = NULL;
        return result;
    }
    
    //Requires : stack != NULL for all Stack functions
    bool isEmpty(Stack stack){
        return stack->top == NULL;
    }
    
    void push(Stack stack, long int data){
        node Last = stack->top;
        node New = malloc(sizeof(struct node));
        New->val = data;
        New->next = Last;
        stack->top = New;
    }
    
    long int pop(Stack stack){
        node last = stack->top;
        stack->top = last->next;
        long int result = last->val;
        free(last);
        return result;
    }
    
    char* cleanup(char *s, size_t length, size_t *result) {
    	char *workspace = calloc(sizeof(char),length);
    	size_t j = 0;
    	for (size_t i = 0; i < length; i++) {
    		if (s[i] != ' ') {
    			workspace[j] = s[i];
    			j++;
    		}
    	}	
    	*result = j;
    	return workspace;
    }
    
    int calculate(char *s) {
    	if (s == NULL || *s == '\0') {
    		return 0;
    	}
    	size_t length = 0;
    	s = cleanup(s, strlen(s), &length);
    	Stack stack = New();
    	char *cursor = s;
    
    	//here we need to handle the situation where the formula begins with a sign, and read in the first number
    	if (s[0] == '-') {
    		cursor++;
    		push(stack, -strtol(cursor,&cursor, 0));
    	}
    	else{
    		if (s[0] == '+') {
    			cursor++;
    		}
    		push(stack, strtol(cursor,&cursor, 0));
    	}
    
    	//From here on whenever we enter the loop the string should begin with a sign, otherwise the formula is not well-formed
    	while (cursor != &s[length]) {
    		if (*cursor == '-') {
    			cursor++;
    			push(stack, -strtol(cursor, &cursor, 0));
    		}
    		else if (*cursor == '+') {
    			cursor++;
    			push(stack, strtol(cursor,&cursor, 0));
    		} 
    		else if (*cursor == '*') {
    			cursor++;
    			push(stack, pop(stack) * strtol(cursor, &cursor, 0));
    		}
    		else {
    			cursor++;
    			push(stack, pop(stack) / strtol(cursor, &cursor, 0));
    		}
    	}
    
    	//Here we should have eliminated all times and divides
    	long int result = 0;
    	while (!isEmpty(stack)) {
    		result += pop(stack);
    	}
    	return (int)result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.