Thread: Linked Lists please help!!!

You can't even think about a linked list, if you aren't able to get the equation from the user.

This

Code:

int main()
{
    char eq;
    ...
    scanf("%s", &eq);

doesn't work because you declare "eq" as a char, i.e. you can only store a single character in it.

Strings in C are special char arrays terminated with '\0'.
Do you know how to declare a char array?

For a start try to make a program which reads a string from the user and then loop through the string and print every single character. I recommend using fgets() for the reading part because scanf("%s") only reads until the first whitespace character. Is the user allowed to use spaces between operands/operators?

Generally, you should always work on a program like that. Work on one small part and only continue to the next when you are sure that everything works. Read also A development process.
Compile often and turn on all compiler warnings and learn to understand them.

Bye, Andreas

Is it easier to tell the user to give one by one the characters of the string or by telling him to give all the string one time?? I am asking that because i thing that is a little bit more difficult to tell the user to give the string one time and from that string to choose only the parenthesis. Am i right???

The user will always enter a full line. Your program won't see the input until the user presses Enter.

Actually your idea of reading the input character by character is even better than mine. :-)
So your main() should have a loop which reads a character from the input until the newline character or EOF. For each character you decide if you add it to the list (opening parenthesis), remove it from the list (closing parenthesis) or just ignore it.

For using the linked list as a stack you need three functions:
push: will add one parenthesis/node at the beginning/top of the list (that's the easiest way)
pop: will remove one parenthesis/node from the beginning/top if there is still one in the list.
is_empty: will test if the list is empty.

Inside the loop, if you try to pop a parenthesis from an empty list/stack, then you know there is a missing opening parenthesis
If there is still a parenthesis on the stack after the loop, a closing parenthesis is missing.
Otherwise, the expression is valid.

Bye, Andreas

Can anyone tell me if it's possible how i can use the function strlen() to find the length of a string that i don't know? (i mean that the string is given by the user so is unknown).

Yes - "strlen()" gives you the length of the string whether you "know it" or not.

In 'C', a string is an array of characters terminated by a null character ('\0').

That null character is what the 'C' string functions depend upon. So if a user enters a string, and it's stored in an array, or in memory allocated dynamically, "strlen()" will determine the length of the string (based on the null character) and tell you (but, mind you, it doesn't include the null character in the count). .

Hello again, i tried to make the program in this way telling the user to give one by one the character of the equation and not the full equation at once but i still have some problems.
Actually i did this in main:

Code:

int main()
{
    char character;
    int found = 1;

    do
    {
        printf("Please give a character : ");
        scanf("%c", &character);
        printf("\n");

        if(character == '(')
        {
            insert(character);
        }
        else if(character == ')')
        {
            Delete();
        }
        
    }while(found != 0);
    
    empty_list(); // If the list is empty then i print the message the equation is true else the equation is false.

return 0;
system ("pause");

}

but i still face some problems. Can you help me to solve this one?

Originally Posted by ValL

i tried to make the program in this way telling the user to give one by one the character of the equation and not the full equation at once but i still have some problems.

You really don't have to tell the user to enter the expression character by character. Let the user enter the whole expression.

Usually standard input is line buffered, i.e. as long as the user doesn't press the enter key, your program won't see anything of the input. The input is stored by the OS in an internal buffer.
Only after pressing the enter key, your program can access the contents of the buffer.

A typical loop, which reads a line character by character looks like

Code:

int ch;
while ((ch = getchar()) != '\n')
    // do stuff with the character stored in ch

getchar() reads the next character from the input stream and stores it in "ch". The loop continues until the next newline character (from pressing the enter key) is read.

Bye, Andreas

Here i am again. I have tried so hard to make my program work but still nothing. Finally i have decided to make the program asking the user to give the full equation and then make the check.

So i need one more time your help for this one.

i have tried to do this but i am not sure where is the error can you help me?

Code:

int main()
{
    char exp[MAX];
    Head = NULL;
    int i = 0;

    printf("Please give the equation you want: ");
    gets(exp);

    while(exp[i] != '\n' )
    {
        if(exp[i] == '(' )
        {
            insert(exp[i]);
        }
        else if(exp[i] == ')' )
        {
            Delete();
        }

        i++;
    }

    empty_list();

return 0;
system ("pause");
}

is it ok the way i have it... I will appreciate every small help!!

Originally Posted by ValL

i have tried to do this but i am not sure where is the error can you help me?

Don't use gets!

What are your errors? Compiler warnings, program crash, wrong result?
You only show us your main(), but what about insert(), Delete() and empty_list()?

Bye, Andreas

Actually i have change it lots of times but i can't find the actual answer.
I am so confused and disappointed because every change i have tried doesn't work.

I am sending you another time my answer and i hope this time to find the correct answer.

Code:

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

struct Node
{
    char Data;
    struct Node *Next;
}*Head;


void insert(char c)
{
  struct Node *new_node, *old_node;

  new_node = (struct Node *)malloc(sizeof(struct Node));
  new_node->Data = c;

  old_node = Head;

  if(Head == NULL)
  {
      Head=new_node;
      Head->Next=NULL;
  }
  else
  {
      while(old_node->Next != NULL)
      old_node = old_node->Next;

      new_node->Next = NULL;
      old_node->Next = new_node;
  }

}

void Delete()
{
    struct Node *last;
    last = (struct Node *)malloc(sizeof(struct Node));
    last = Head;

    struct Node *previous_last;
    previous_last = (struct Node *)malloc(sizeof (struct Node));

    while(last->Next != NULL)
    {
        previous_last = last;
        last = previous_last->Next;
    }
    previous_last->Next = NULL;
    free(last);
    printf("\n");

}

void empty_list()
{
    struct Node *pointer;
    pointer = Head;

    if (pointer == NULL)
    {
        printf("The equation is correct");
        printf("\n");
    }
    else
    {
        printf("The equation is incorrect");
        printf("\n");
    }

}

int main()
{
    Head = NULL;
    int i = 0;
    char ch;
    int found = -1;

    while(found != 0)// Here in while loop i don't know if is better to put while(ch != EOF) or while(found != 0) please tell me what's better
    {
        printf("Give a character you want: "); //I wand this message to be printed for every single character tha's why i put it in the loop
        scanf("%c", &ch);
        printf("\n");

        if(ch == '(')
        {
            insert(ch); // call insert function

        }
        else if(ch == ')')
        {
            Delete();//call delete function
        }

        i++;
        found = 0 //I make found=0 to make the while loop stop 
    }
    empty_list(); // I call the empty list to print the messages 

return 0;
system ("pause");
}

This is all my cote, i will uppreciate everything you will tell me!!

Thank you again

Anyone ???

Originally Posted by ValL

Actually i have change it lots of times but i can't find the actual answer.
I am so confused and disappointed because every change i have tried doesn't work.

It looks like you have written the whole program in one session and are now randomly modifying parts to get it right. I can assure you this method doesn't work.
Why haven't you read the link about how you should develop a program (one small part after another)?

You are still trying to prompt the user for every single character. I don't think that's a good way but it is your decision.

Your insert() looks okay. IMHO it's way easier to just add every new node at the front but (again) it's your decision.

Your Delete() (BTW: why are some of your variable/function names starting with a lowercase letter and others with an uppercase letter?) has two errors:

Code:

struct Node *last;
last = (struct Node *)malloc(sizeof(struct Node));
last = Head;

You allocate memory for "last" and on the next line you assign "Head" to it, thus throwing away all references to the allocated memory block (in other words you are leaking memory). If you want that "last" points to "Head" you don't need to allocate memory for "last".
You do the same thing with "previous_last".

Code:

struct Node *previous_last;
previous_last = (struct Node *)malloc(sizeof (struct Node));

while(last->Next != NULL)
{
    previous_last = last;
    last = previous_last->Next;
}
previous_last->Next = NULL;
free(last)

Here you have two problems:
1) If your list is empty ("Head" and "last" will be NULL - this happens when the user enters a closing parenthesis before any opening one) you try to dereference a NULL pointer in your while condition.
2) When there is only one node in the list, "last->Next" will point to NULL, so the while-loop doesn't execute. The following assignment to "previous_last->Next" is practically useless because you haven't assigned any node from the list to "previous_last". But more seriously you free "last" and simultaneously "Head". Hence any reference to "Head" later in the program (for example if you want to add a new opening parenthesis by calling insert()) is invalid because "Head" points now to a freed memory block.

IMHO your Delete() would be easier if you would have added the new nodes at the beginning. But it's your decision.

Instead of printing the final messages, your empty_list() should better be named is_empty() and should return true if the list is empty and false if not. You need such a function in case the user enters more closing parenthesis than opening ones. Then you shouldn't remove any node but break out of the main loop.
You will also need it at the end of the main loop to check if the list is empty (otherwise the user has entered too many opening parenthesis).
In pseudocode your loop in main should look like:

Code:

correct = true
while there are characters to process
    if character is '('
        push character (add it to the list)
    if character is ')'
        if list is empty
            correct = false
        else
            pop character (remove parenthesis from the list)

if list is not empty
    correct = false

if correct
    print "Expression is correct"
else
    print "Expression is incorrect"

Generally I wouldn't use a global variable for "Head" but declare it local to main() and pass it to the functions. But again, it's your decision.

Bye, Andreas

Thank you very much my friend for your help. I really found it very helpful!!