Undefined computer behavior after running a C program

Question

I am getting right to the point because I cannot explain the situation that I am going to describe. I need your attention please!

Yesterday I wrote a program in C. The program takes as input a string and if that string is in this form "PKPKKKPPPKKKP", namely consists only 'P' and 'K' character it prints you YES or NO. YES if for a single 'P' character there is a match with a 'K' character. Exactly as we do with parenthesis characters problem '(', ')', only instead of '(' I had to use 'P' and instead of ')', 'K'.

With a little help from here I managed to finish the program and it was running correctly. I do not think that copying the code will help anyone, but I will explain how it works.

Program Description: The program takes a string (the string can be up to 500 length) as input, if the string consists only 'P' and 'K' characters it prints YES or NO, as I described above, otherwise it rejects it. Then it reads the input, character by character, and when it finds 'P' it is pushed in a stack, else pop. (I implemented the stack with linked list, so the user will be able to give as big a string he wants (or I thought so...)). Before the user typed a string, the symbol 'A' was in the stack. So the input was analyzing by the program, character by character and if it found a 'P' it was pushed to the stack, else pop the stack. If the top of the stack at the end was the 'A' character, the program was printing YES, else NO.

Problem Description: So I am with a friend of mine today,performing the program. Everything was ok. Until I pass as an input a really big string, like 300'P's and 300'K's (and remember my string is a char string[500]). It printed yes. Then I typed a string like 800'P's+800'K's. It didn't run correctly. Here is the problem, after that incident whatever if I type a string, a normal one "PKPKPK", it prints millions of weird symbols ( x └ X ╨ x └ X ╨ x ). I haven't touch the code, I swear! I compiled again, run again, the same! Its like something is wrong with my pc (Windows 10). And the problem continues to another program...I tried to make a a simple program just to function a stack implemented with linked list. I pushed the character 'a' and print it. It prints 'á'. I pushed the 'b'. It prints 'h'. I pushed the 'd'. It prints 'L'.

Obviously I should not have typed such a huge string because the limit of its length was 500. But the problem still exists! I cannot write a program with linked list anymore. I am desperate!

The code:

#include "stdio.h"
#define FIRST_SYMBOL_IN_STACK 'A'
#define TRUE 1
#define FALSE 0
#define STR_LENGTH 50
#define YES "YES"
#define NO "NO"
#define PLA 'P'
#define KAL 'K'

typedef struct node {
    char simvolo_eisodou;
    struct node *next;
} node; 

node *top = NULL; // the top of the stack

void push(char simvolo_eisodou); //stack function
int isStackEmpty(); //stack function
void pop(); //stack function
void printStack(); //print the current stack elements
int isInputValid(char *string); 
void printWelcome();

int main() {
    char input_string[STR_LENGTH], apantisi = 'G';  //O xristis mporei na dwsei input_string mikous ews 500 xaraktires
    push(FIRST_SYMBOL_IN_STACK);
    int i = 0;
    scanf("%s", input_string);

    if (isInputValid(input_string)) {
        while (input_string[i] != '\0') {
            if (input_string[i] == PLA) {
                push(PLA);
                printStack();
            } else {
                pop();
                printStack();;
            }
            i++;
        }
    } else {
        printf("Den anagnwristike to %s, input_string=(P|K)*\n");
        _exit(-1);
    }

    if (top->simvolo_eisodou == FIRST_SYMBOL_IN_STACK) {
        printf("%s\n", YES);
    } else {
        printf("%s\n", NO);
    }

    return 0;
}

void push(char simvolo_eisodou) {
    node *newNode = (node*)malloc(sizeof(node));
    newNode->simvolo_eisodou = simvolo_eisodou;
    newNode->next = top;
    top = newNode;
    free(newNode);
}

int isStackEmpty() { //Thewrw oti i stoiva einai adeia otan i korifi einai to arhiko simvolo
    if (top->simvolo_eisodou == FIRST_SYMBOL_IN_STACK) {
        return TRUE;
    }
    return FALSE;
}

void pop( ){
    if (isStackEmpty()) {
        printf("KENO\n");
        printf("%s\n", NO);
        _exit(-1);
    }
    node *temp = top;
    top = top->next;
    free(temp);
}

void printStack() {
    node *current = top;
    while (current != NULL) {
        printf("%c ", current->simvolo_eisodou);
        current = current->next;
    }
    free(current);
    printf("\n");
}

int isInputValid(char *string) {
    int i = 0;
    while (*(string + i) != '\0') {
        if (!(*(string + i) == 'P' || *(string + i) == 'K')) {
            return 0;
        }
        ++i;
    }
    return 1;
}

void printWelcome() {
    printf("\n====================================================================\n");
    printf("Welcome\n");
    printf("====================================================================\n");
    printf("\n\n\n Plz type input_string=(P|K)*\n");
}

Answer 1

Your code has Undefined Behaviour (UB). The result of running code with UB is unpredictable. It can sometimes appear to work but there is no guarantee that the same result will occur each and every time.

At least one source of your UB is this code:

top=newNode;
free(newNode);

Once newNode is freed the top pointer becomes invalid and any dereferencing of that pointer will result in UB.

Answer 2

Your code starts off with:

#define STR_LENGTH 50

// ...  in main
char input_string[STR_LENGTH];
scanf("%s", input_string);

In your question you talk about a buffer of length 500. But there is no such buffer in your code, the length is 50.

If you type in 50 or more characters then you cause undefined behaviour. This means that anything can happen. There is no possible way you can control what happens in this case and you should not expect any particular behaviour.

The only way to fix the problem is to stop overflowing the buffer. You must change your code so that there is no overflow.

Your program description is that it should support up to 500 characters in the string. One way to achieve this would be:

char input_string[501];   // +1 for terminator
scanf("%500s", input_string);   // IMPORTANT: 500 limiter

If you wanted to report an error if they typed too much, instead of just ignoring it, you could then write:

if ( !isspace(getchar()) )    // requires #include <ctype.h>
{
    fprintf(stderr, "Too many characters entered - aborting program");
    exit(EXIT_FAILURE);
}

for example.

If you actually want to support an arbitrary length of input then you would need to switch to a more complicated memory strategy (e.g. a linked list, or reallocating a buffer as the input grows).

---

Other notes on your code:

• You use functions from #include <stdlib.h> so you must have that line
• printf("Den anagnwristike to %s, input_string=(P|K)*\n") has a %s but no corresponding argument, this also causes undefined behaviour
• Use exit(EXIT_FAILURE) instead of _exit(-1);

NB. There may be other issues as well, I didn't check your whole program.