Search for matching parenthesis

Question

So my background is not CS and I picked up programming as a hobby. Anyway, I need to solve this problem: Given an expression like "([])", check if this expression has matching parenthesis style, i.e matching "[" and matching "(".

I do realize that there are solutions for this but those deal with stack and I have not learned about it. So I attempted my own, which looks very spaghetti but it works.

/* Program to check if parens are balanced */

#include <stdio.h>
#include <string.h>

int main(){

  char expr[100] = "[)";

  int roundcounter = 0, squarecounter = 0, i = 0;

  while (expr[i] != '\0') {
    if (expr[i] == '(') {
      roundcounter++;
    }
    else if (expr[i] == ')') {
      roundcounter--;
      if (roundcounter < 0) {
    break;
      }
    }


    if (expr[i] == '[') {
      squarecounter++;
    }
    else if (expr[i] == ']') {
      squarecounter--;
      if (squarecounter < 0) {
    break;
      }
    }

    i++;
  }

  if (roundcounter == 0 && squarecounter == 0) {
    printf("Balanced parenthesis !\n");
  }

  else {
      printf("Unbalaced !\n");      

      /* Error for [ ] */
      if (squarecounter > 0) {
    printf("Missing right square bracket\n");
      }
      else if (squarecounter < 0) {
    printf("Missing left square bracket\n");
      }

      /* Error for ( ) */
      if (roundcounter > 0) {
    printf("Missing right round bracket\n");
      }
      else if (roundcounter < 0) {
    printf("Missing left round bracket\n");
      }
  }
  return 0;
}

Basically, there are two counters and each responsible for comparing () and [] and increase (+1) if left parens or decrease (-1) if right parens. If counters = 0 then we have balance expression.

Is there a better way to do this? I was thinking of creating a close and open char array:

char openarr[] = {'[', '('};
char closenarr[] = {']', ')'};

But then I am not sure how to proceed. I can loop through the openarr and say if expr[i] matches openarr then increase counter, and do the same for closearr.

However, we still need more than 1 counter because of the following case. Say we have expr = "[)" and only 1 counter, say x.

For loop for openarr will pass because: expr[i] has [ element, counter = 1
For loop for closearr will pass because: expr[i] has ) element, counter = 0

This is certainly not the case for expr = "[)"

Please let me know how to improve this.

Answer 1

The problem you have got with your solution is that you need to remember the order you encountered the open parentheses and brackets. I recommend you just have one counter that you increment when you encounter [ or ( and decrement when you encounter ] or ) and you have an array which records which type of bracket you encountered when the count was whatever.

The solution below keeps an array of which type of bracket is required to match when you decrement the bracket count. If, when you decrement the bracket count, it gets the wrong type of bracket, that's a no match.

    char expr[100] = "[([)][]]";
    char brackets[100]; // In a real application, allocate dynamically to the same length as the string
    int bracketCount = 0;
    for (int i = 0 ; i < 100 || expr[i] == '\0' ; ++i)
    {
        if (expr[i] == '[' || expr[i] == '(') 
        {
            // Record the type of *closing* bracket we expect when we get back
            // down to this bracket count
            brackets[bracketCount] = expr[i] == '[' ? ']' : ')';
            bracketCount++;
        }
        else if (expr[i] == ']' || expr[i] == ')')
        {
            bracketCount--;
            if (bracketCount < 0 || brackets[bracketCount] != expr[i] )
            {
                printf("Unmatched\n");
                return 1;
            }
        }
    }
    if (bracketCount > 0)
    {
        printf("Unmatched\n");
        return 1;
    }
    printf("matched\n");
    return 0;

There you are: a solution without a stack in sight¹.

¹ OK I lied, it does use a stack. The array brackets and the int bracketCount form a stack.

Answer 2

As it has been answered, you need an stack in order to be able to match the parenthesis themselves. the idea is to push the parenthesis into the stak when they are left (if you get a [ you push it, or if you encounter a left ( you push it) When you find a right ] or ), then you pop the character at the pop of the stack and see if it is the same type as the one you have encountered... if they are the same type, then they match, and you throw both and proceed to the next. If at some point you try to pop from the stack and the stack is empty, or you get to the end of the input and the stack still have some contents... then your parenthesis are not balanced, and you have got a mistake. Let's check this algorithm with the following input:

[(])

your first character is a left [, so you push it, giving you this stack:

[

when you read the next char, as it is a left (, you push it, getting this stack:

[(

when the next character comes, a ], you pop your last character, and get a (, and they don't match... you got a failure at that point... indeed that's the first character that doesn't match.

Let's try another example:

[()]]

first, you push [, then you push (, then you get ) and you pop (, getting a matching pair. The stack contents at this point is:

[

then you get the next char, a ] that matches with the top of statck (you pop a [, leaving the stack empty) When the next character arrives (a ]) you pop the stack for a matching [, but you get that the stack is empty, so you signal an error telling that there's an unpaired right ] in the input.

Answer 3

It is not possible to do this correctly without a stack under one form or another. The way you are doing it does not cope correctly with nestings. For example it will incorrectly accept "[(])"