Sample C code submission using Linked list based stack


  • 0
    V
    struct node {
    	char a;
    	struct node *next;
    };
    
    
    void insertAtTop(struct node **head, char value) {
    	struct node *temp = (struct node*)malloc(sizeof(struct node));
    	temp->a = value;
    	temp->next = (*head);
    	(*head) = temp;
    }
    
    char popFromTop(struct node **head) {
    	if(!(*head)){
            return '!';
        }
        char a = (*head)->a;
    	struct node *temp = (*head);
    	(*head) = (*head)->next;
    	free(temp);
    	return a;
    }
    
    bool freeStack(struct node *head) {
    	bool empty = true;
    	struct node *temp = head;
    	struct node *temp1;
    	while (temp) {
    		temp1 = temp;
    		temp = temp->next;
    		free(temp1);
    		empty = false;
    	}
    	return empty;
    }
    
    char returnOpenParanthesis(char closingParanthseis) {
    	switch (closingParanthseis)
    	{
    	case ')': 
    		return '(';
    	case '}':
    		return '{';
    	case ']':
    		return '[';
    
    	default:
    		return '!';
    	}
    }
    bool OpenParanthesis(char paranthesis) {
    	if (paranthesis == '(' || paranthesis == '{' || paranthesis == '[') {
    		return true;
    	}
    	return false;
    }
    
    
    bool isValid(char* s) {
    	if (strlen(s) < 2) {
    		return false;
    	}
        struct node *stackHead = (struct node*)malloc(sizeof(struct node));
    	if (!OpenParanthesis(s[0])) {
    		return false;
    	}
    	stackHead->a = s[0];
    	stackHead->next = NULL;
    	int len = strlen(s);
    	int i;
    	bool insert = false;
    	char expected;
    	char observed;
    	for (i = 1; i < len; i++) {
    		if (OpenParanthesis(s[i])) {
    			insertAtTop(&stackHead, s[i]);
    		}
    		else {
    			expected = returnOpenParanthesis(s[i]);
    			observed = popFromTop(&stackHead);
    			if (expected != observed) {
    				freeStack(stackHead);
    				return false;
    			}
    		}
    	}
    	if (!freeStack(stackHead)) {
    		return false;
    	}
    	return true; 
    }
    

Log in to reply
 

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