3ms C solution using stack


  • 0
    Z

    implement linked list and stack(based on linked list)

    #define ElementType int
    #define INT_NULL -99999
    
    typedef struct LinkedList_Node *LinkedList_PtrToNode;
    typedef struct LinkedList_Node *LinkedList_List;
    typedef struct LinkedList_Node *LinkedList_Position;
    
    struct LinkedList_Node
    {
    	ElementType Element;
    	LinkedList_PtrToNode Next;
    };
    
    LinkedList_List LinkedList_CreateEmptyList()
    {
    	LinkedList_List list = (LinkedList_List)malloc(sizeof(struct LinkedList_Node));
    	list->Next = NULL;
    	return list;
    }
    
    int LinkedList_IsEmpty(LinkedList_List list)
    {
    	if(list->Next==NULL)
    		return 1;
    	else
    		return 0;
    }
    
    void LinkedList_MakeEmpty(LinkedList_List list)
    {
    	LinkedList_Position position;
    	while(list->Next!=NULL){
    		position = list->Next;
    		list->Next = list->Next->Next;
    		free(position);
    	}
    }
    
    void LinkedList_DeleteList(LinkedList_List list)
    {
    	LinkedList_MakeEmpty(list);
    	free(list);
    }
    
    int LinkedList_Length(LinkedList_List list)
    {
    	int result = 0;
    	LinkedList_Position position = list->Next;
    	while(position!=NULL){
    		result++;
    		position = position->Next;
    	}
    	return result;
    }
    
    void LinkedList_InsertFront(LinkedList_List list, ElementType value)
    {
    	LinkedList_Position position = (LinkedList_Position)malloc(sizeof(struct LinkedList_Node));
    	position->Element = value;
    	position->Next = list->Next;
    	list->Next = position;
    }
    
    void LinkedList_InsertEnd(LinkedList_List list, ElementType value)
    {
    	LinkedList_Position position = (LinkedList_Position)malloc(sizeof(struct LinkedList_Node));
    	position->Element = value;
    	position->Next = NULL;
    	LinkedList_Position tempPosition = list;
    	while(tempPosition->Next!=NULL){
    		tempPosition = tempPosition->Next;
    	}
    	tempPosition->Next = position;
    }
    
    void LinkedList_DeleteFront(LinkedList_List list)
    {
    	LinkedList_Position position = list->Next;
    	if(position!=NULL){
    		list->Next = list->Next->Next;
    		free(position);
    	}
    }
    
    void LinkedList_DeleteEnd(LinkedList_List list)
    {
    	LinkedList_Position position = list;
    	if(position->Next==NULL)
    		return;
    	while(position->Next->Next!=NULL){
    		position = position->Next;
    	}
    	free(position->Next);
    	position->Next = NULL;
    }
    
    ElementType LinkedList_FindNthValue(LinkedList_List list, int N)
    {
    	LinkedList_Position position = list->Next;
    	while(position!=NULL && N>1){
    		position = position->Next;
    		N--;
    	}
    	if(N==1 && position!=NULL)
    		return position->Element;
    	else
    		return INT_NULL;
    }
    
    LinkedList_Position LinkedList_FindNthPosition(LinkedList_List list, int N)
    {
    	LinkedList_Position position = list->Next;
    	while(position!=NULL && N>1){
    		position = position->Next;
    		N--;
    	}
    	if(N==1 && position!=NULL)
    		return position;
    	else
    		return NULL;
    }
    
    void LinkedList_Print(LinkedList_List list)
    {
    	LinkedList_Position position = list->Next;
    	printf("list: ");
    	while(position!=NULL){
    		printf("[%d]->", position->Element);
    		position = position->Next;
    	}
    	printf("end\n");
    }
    
    typedef struct LinkedList_Node *Stack_Position;
    typedef struct LinkedList_Node *Stack;
    
    Stack Stack_Create(void)
    {
    	Stack s = (Stack)malloc(sizeof(struct LinkedList_Node));
    	s->Next = NULL;
    	return s;
    }
    
    int Stack_Size(Stack stack)
    {
    	int result = 0;
    	Stack_Position position = stack->Next;
    	while(position!=NULL){
    		result++;
    		position = position->Next;
    	}
    	return result;
    }
    
    void Stack_MakeEmpty(Stack stack)
    {
    	Stack_Position position;
    	while(stack->Next!=NULL){
    		position = stack->Next;
    		stack->Next = stack->Next->Next;
    		free(position);
    	}
    }
    
    void Stack_DeleteStack(Stack stack)
    {
    	Stack_MakeEmpty(stack);
    	free(stack);
    }
    
    ElementType Stack_Top(Stack stack)
    {
    	if(stack->Next==NULL)
    		return INT_NULL;
    	else
    		return stack->Next->Element;
    }
    
    void Stack_Push(Stack stack, ElementType value)
    {
    	Stack_Position position = (Stack_Position)malloc(sizeof(struct LinkedList_Node));
    	position->Element = value;
    	position->Next = stack->Next;
    	stack->Next = position;
    }
    
    void Stack_Pop(Stack stack)
    {
    	Stack_Position position;
    	if(stack->Next!=NULL){
    		position = stack->Next;
    		stack->Next = stack->Next->Next;
    		free(position);
    	}
    }
    
    void Stack_Print(Stack stack)
    {
    	Stack_Position position = stack->Next;
    	printf("stack: ");
    	while(position!=NULL){
    		printf("[%d]->", position->Element);
    		position = position->Next;
    	}
    	printf("end\n");
    }
    
    bool isValid(char* s)
    {
    	Stack stack = Stack_Create();
    	int top;
    	int len = strlen(s);
    	int i;
    	for(i=0;i<len;i++){
    		top = Stack_Top(stack);
    		if(top==INT_NULL){
    			Stack_Push(stack, s[i]);
    			printf("push %c\n",s[i]);
    		}
    		else if((top=='[' && s[i]==']') || (top=='(' && s[i]==')') || (top=='{' && s[i]=='}')){
    			printf("pop %c\n", Stack_Top(stack));
    			Stack_Pop(stack);
    		}
    		else{
    			Stack_Push(stack, s[i]);
    			printf("push %c\n",s[i]);
    		}
    	}
    	bool result = Stack_Top(stack)==INT_NULL;
    	Stack_DeleteStack(stack);
    	return result;
    }
    

Log in to reply
 

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