Check if the input string consisting of braces is well-formed

Question

I have spent the last two hours trying to debug my code that is supposed to check if the input consists of well-formed brackets. What I mean by well formed is that ()()[] or ([()]) are acceptable but ((((() is not.

I'm not allowed to use any header file apart from <stdio.h>

#include <stdio.h>

void cross(char str[], int i, int j) {
    str[i] = 'X';
    str[j] = 'X';
}

int iscrossed(char str[]) { 
    int i = 0;
    while (str[i] != '\0') {
        if (str[i] != 'X')
            return 0;
        i++;
    }
    return 1;
}

int check(char str[]) {
    int i = 1, j;
    while (str[i] != '\0') {
        if (str[i] == ')') {
            for (j = i - 1; j >= 0; j--) {
                if (str[j] == '(') {
                    cross(str, str[i], str[j]);
                }
                break;
            }
        } else
        if (str[i] == ']') {
            for (j = i - 1; j >= 0; j--) {
                if (str[j] == '[') {
                    cross(str, str[i], str[j]);
                }
                break;
            }
        }
        i++;
    }
    if (iscrossed(str) == 1)
        return 1;
    else
        return 0;
}

int main() {
    char str[20];
    scanf("%s", str);
    printf("%d\n", check(str));
}

For certain inputs the program prints a zero followed by a segmentation fault and for the others it just prints a zero. Please keep in mind that I'm a beginner programmer so please don't include too much heavy stuff in your hints. I'd be grateful for any help on this.

Edit: It would be wonderful if your answer tells me the errors in my code, because that was my question in the first place.

Answer 1

There are multiple problems in your code:

• you call cross(str, str[i], str[j]); instead of cross(str, i, j); when you find matches for parentheses and brackets.
• the break statement should be moved inside the if block.
• your method does not allow detection of nesting errors
• your method would have undefined behavior if str is an empty string (which you cannot input via scanf())

Here is a modified version:

#include <stdio.h>

void cross(char str[], int i, int j) {
    str[i] = str[j] = 'X';
}

int iscrossed(char str[]) { 
    int i = 0;
    while (str[i] != '\0') {
        if (str[i] != 'X')
            return 0;
        i++;
    }
    return 1;
}

int check(char str[]) {
    int i = 0, j;
    while (str[i] != '\0') {
        if (str[i] == ')') {
            for (j = i - 1; j >= 0; j--) {
                if (str[j] == '(') {
                    cross(str, i, j);
                    break;
                }
            }
        } else
        if (str[i] == ']') {
            for (j = i - 1; j >= 0; j--) {
                if (str[j] == '[') {
                    cross(str, i, j);
                    break;
                }
            }
        }
        i++;
    }
    return iscrossed(str);
}

int main() {
    char str[80];
    if (scanf("%79s", str) == 1) {
        printf("%d\n", check(str));
    }
    return 0;
}

Here is a simpler alternative:

#include <stdio.h>

const char *check(const char str[], int endc) {
    while (str) {
        int c = *str++;
        switch (c) {
          case '(': str = check(str, ')'); break;
          case '[': str = check(str, ']'); break;
          case '{': str = check(str, '}'); break;
          case ')':
          case ']':
          case '}':
          case '\0': return c == endc ? str : NULL;
        }
    }
    return NULL;
}

int main() {
    char str[80];
    if (fgets(str, sizeof str, stdin)) {
        printf("%d\n", check(str, '\0') != NULL);
    }
    return 0;
}

Answer 2

Here a simple recursive solution:

#include <stdio.h>

int brace(const char **s, char cc)
{
  while(1) {
    if(**s == cc) { return 0; }
    switch(**s) {
      case '\0': return -1;
      case '[': ++(*s); if(brace(s, ']')) { return -1; } ++(*s); break;
      case '{': ++(*s); if(brace(s, '}')) { return -1; } ++(*s); break;
      case '(': ++(*s); if(brace(s, ')')) { return -1; } ++(*s); break;
      case ']':
      case '}':
      case ')': return -1;
      default: ++(*s);
    }
  }
}

int check_brace(const char *s)
{
  return brace(&s, '\0');
}


int main()
{
  printf("%d\n", check_brace(" hekl(l o{ asdf } te)ts()({})"));
}

Returns -1 when somethings wrong. Otherwise 0.

Answer 3

If its ok for you to use stdlib.h then,

#include <stdio.h>
#include <stdlib.h>
#define bool int

// structure of a stack node
struct sNode {
    char data;
    struct sNode* next;
};

// Function to push an item to stack
void push(struct sNode** top_ref, int new_data);

// Function to pop an item from stack
int pop(struct sNode** top_ref);

// Returns 1 if character1 and character2 are matching left
// and right Brackets
bool isMatchingPair(char character1, char character2)
{
    if (character1 == '(' && character2 == ')')
        return 1;
    else if (character1 == '{' && character2 == '}')
        return 1;
    else if (character1 == '[' && character2 == ']')
        return 1;
    else
        return 0;
}

// Return 1 if expression has balanced Brackets
bool areBracketsBalanced(char exp[])
{
    int i = 0;

    // Declare an empty character stack
    struct sNode* stack = NULL;

    // Traverse the given expression to check matching
    // brackets
    while (exp[i])
    {
        // If the exp[i] is a starting bracket then push
        // it
        if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
            push(&stack, exp[i]);

        // If exp[i] is an ending bracket then pop from
        // stack and check if the popped bracket is a
        // matching pair*/
        if (exp[i] == '}' || exp[i] == ')'
            || exp[i] == ']') {

            // If we see an ending bracket without a pair
            // then return false
            if (stack == NULL)
                return 0;

            // Pop the top element from stack, if it is not
            // a pair bracket of character then there is a
            // mismatch.
            // his happens for expressions like {(})
            else if (!isMatchingPair(pop(&stack), exp[i]))
                return 0;
        }
        i++;
    }

    // If there is something left in expression then there
    // is a starting bracket without a closing
    // bracket
    if (stack == NULL)
        return 1; // balanced
    else
        return 0; // not balanced
}

// Driver code
int main()
{
    char exp[100] = "{()}[]";

    // Function call
    if (areBracketsBalanced(exp))
        printf("Balanced \n");
    else
        printf("Not Balanced \n");
    return 0;
}

// Function to push an item to stack
void push(struct sNode** top_ref, int new_data)
{
    // allocate node
    struct sNode* new_node
        = (struct sNode*)malloc(sizeof(struct sNode));

    if (new_node == NULL) {
        printf("Stack overflow n");
        getchar();
        exit(0);
    }

    // put in the data
    new_node->data = new_data;

    // link the old list off the new node
    new_node->next = (*top_ref);

    // move the head to point to the new node
    (*top_ref) = new_node;
}

// Function to pop an item from stack
int pop(struct sNode** top_ref)
{
    char res;
    struct sNode* top;

    // If stack is empty then error
    if (*top_ref == NULL) {
        printf("Stack overflow n");
        getchar();
        exit(0);
    }
    else {
        top = *top_ref;
        res = top->data;
        *top_ref = top->next;
        free(top);
        return res;
    }
}

Features

• Support nested parantheses like (())
• Support bad nestings such as ([)]
• Commented but not by me (see the below spoiler)

Note: i feel guilty that i have copied code from here

The algorithm

Pseudocode Like Block code!

If it's not ok for you to use stdlib.h,then someone may edit this code and remove the errors that occur when we remove that line(#include <stdlib.h>),I am not a c guy and i don't know to edit,i just copy pasted !

Answer 4

First attempt didn't worked with bad nesting, as MOehm wrote in the comments. Storing the opened braces that not have been closed yet helps to recognize bad nesting. The last opened brace will determine which closing brace is need.

#include <stdio.h>

int check(char str[], int size)
{
    char opened[size/2];
    char close;
    int i = 0;
    int pos = 0;
    int error = 0;
    
    while((i < size) || (pos < size/2))
    {
        if((str[i] == '(') || (str[i] == '['))
        {
            opened[pos] = str[i];
            pos++;
        }
        else if((str[i] == ')') || (str[i] == ']'))
        {
            if(str[i] == close)
            {
                opened[pos-1] = 0;
                pos--;
            }
            else
            {
                error = 1;
                break;
            }
        }
        printf("%s\n", opened);
        if(pos > 0)
        {
            switch(opened[pos-1])
            {
                case '(':
                    close = ')';
                    break;
                    
                case '[':
                    close = ']';
                    break;
            }
        }
        else
            close = 0;
            
        i++;
    }
    return error;
}

int main() {
    char str[20];
    printf("%d\n", check(str, sizeof(str)));
    
    return 0;
}

Answer 5

Pseudocode of a possible answer:

initialize char[] unclosed
int latest_unclosed_index = -1
for each char in string {
   if char == opening_bracket {
      latest_unclosed_index += 1
      unclosed[latest_unclosed_index] = char
   } else if char == closing_bracket {
      if latest_unclosed_index < 0 {
         return false
      } else if char == closing_of(unclosed[latest_unclosed_index]) {
         unclosed[latest_unclosed_index] = null
         latest_unclosed_index -= 1
      } else {
         return false
      }
      
   }
}
if latest_unclosed_index == -1 {
   return true
} else {
   return false
}

This works by keeping an array of all unclosed opening brackets in the order that you encounter them in, and removing them whenever you encounter a closing bracket, as a sort of stack.

This solution has a complexity of O(n).

A problem with this implementation is that there is an unknown amount of brackets in string, which may cause the array to overflow if it isn't large enough.

Solution:

• To be sure that this solution doesn't overflow, the size of the array should be at least half the size of the input string, and you'll have to check at each character if there are enough characters left in the input string to be able to completely close all brackets.
• Use a list implementation (or write your own) instead of an array for unclosed.