Balanced Parenthesis Check

Objective

To check if an entered string containing nested parenthesis are balanced and valid. This write-up presents a function with which a string is checked for balanced parenthesis.

The Process

First a sting of parenthesis or an algebraic equation is input. In this process we are only concerned about the balanced parenthesis, so all the other symbols and characters other than the parenthesis will be ignored. After we get the string the characters from the input string is read one by one. If a starting bracket/parenthesis ‘(‘ or ‘{‘ or ‘[‘ is found then it is pushed in the stack. If an ending bracket/parenthesis ‘)’ or ‘}’ or ‘]’ is found then that top parenthesis symbol is popped from the top of the stack and matched with the current parenthesis. If the two are a match (example: if popped bracket is ‘{‘ and current is ‘}’ then it is a match), then we continue to check the remaining brackets, removing the top symbol as a match is found for that bracket. If the popped bracket is not a match (example: if popped bracket is ‘{‘ and current is anything other than ‘}’ then it is mismatch) then at this point an unbalanced parenthesis is detected, and the process is terminated. If all the characters of the input string is scanned and still the stack is not empty, that is there are still brackets to be matched , then there is a mismatch and the process terminates detecting a mismatch.
Thus pushing, popping and matching the parenthesis a string can be detected as valid or invalid sequence of parenthesis.

FUNCTION check_parenthesis (string str)
/* Default to balanced */
  status = BALANCED
  WHILE str[i] is not NUL
    DO
      'current_token' = str[i]
      IF [ 'current_token' is an opening parenthesis ]
        THEN
          push (current_token)
      ELSE IF [ 'current_token' is a closing parenthesis ]
        THEN
          IF [ stack_is_empty ]
            THEN
              status = NOT_BALANCED
              BREAK
          ENDIF
          'prev_match' = pop ()
          IF [ 'prev_match' is not a matching parenthesis of 'current_token' ]
            THEN
              status = NOT_BALANCED
              BREAK
          ENDIF
      ENDIF
      i = i + 1
  ENDWHILE

/* Check if the stack still have tokens after string terminates */

  IF [ stack_is_not_empty ]
    THEN
        status = NOT_BALANCED
  ENDIF

  IF [ status = BALANCED ]
    THEN
       PRINT “The parenthesized equation if balanced”
    ELSE
      PRINT “The parenthesized equation is NOT balanced”
  ENDIF
ENDFUNCTION

Sourcecode

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

#define TRUE 1
#define FALSE 0
#define MAX 128

typedef struct _stack
{
  char *s;
  int top;
} stack;

void stack_push (stack * s, char c);
char stack_pop (stack * s);
int stack_is_empty (stack * s);
stack *stack_create (int n);
void stack_delete (stack *stk);

int check_balanced_paranthesis (char *exp, int *error_at);

int
main (void)
{
  char exp[MAX] = "";
  int retval, error_at;

  printf ("\n\nCheck for balanced parenthesized equation.");
  printf ("\nEnter paranthesised string :\n");
  scanf (" %[^\n]", exp);

  retval = check_balanced_paranthesis (exp, &error_at);

  if (retval == TRUE)
    printf ("\nParanthesis are UNBALANCED.\nFirst Error at location %d\n",
	    error_at);
  else
    printf ("\nParanthesis are BALANCED\n");

  return 0;
}

/* Accepts an expression exp to check for balanced parenthesis, 
 * other symbols are ignored. The error_at will store the position
 * where the first error was encountered. If NULL is passed in
 * error_at, it will not be considered. In case of an error a 
 * nonzero values is returned, in case of a correct expression a 0
 * is returned.
 */

int
check_balanced_paranthesis (char *exp, int *error_at)
{
  char token = '\0', temp;
  int error = FALSE, i = 0;
  stack *stk;

  stk = stack_create (MAX);

  while (exp[i] != '\0')
    {
      token = exp[i];
      if (token == '(' || token == '{' || token == '[')
	stack_push (stk, token);
      else if (token == ')' || token == '}' || token == ']')
	{
	  if (stack_is_empty (stk))
	    {
	      error = TRUE;
	      break;
	    }
	  temp = stack_pop (stk);

	  if (!((temp == '(' && token == ')') ||
		(temp == '{' && token == '}') ||
		(temp == '[' && token == ']')))
	    {
	      error = TRUE;
	      break;
	    }
	}
      i++;
    }
  if (!stack_is_empty (stk))
    error = TRUE;

  if ((error == TRUE) && (error_at != NULL))
    *error_at = i + 1;

  stack_delete (stk);
  return error;
}

/* STACK ROUTINES START */
void
stack_push (stack * stk, char token)
{
  if (stk->top >= MAX)
    {
      printf ("\nStack FULL Terminating");
      exit (1);
    }
  stk->s[++(stk->top)] = token;
}

char
stack_pop (stack * stk)
{
  if (stk->top <= -1)
    return '\0';
  return stk->s[(stk->top)--];
}

int
stack_is_empty (stack * stk)
{
  if (stk->top <= -1)
    return TRUE;
  return FALSE;
}

stack *
stack_create (int n)
{
  stack *temp;

  temp = malloc (sizeof (stack));
  if (temp == NULL)
    {
      perror ("Terminating\n");
      exit (1);
    }
  temp->s = malloc (sizeof (char) * n);
  if (temp->s == NULL)
    {
      perror ("Terminating\n");
      exit (1);
    }
  temp->top = -1;
  return temp;
}

void 
stack_delete (stack *stk)
{
  if (stk != NULL)
    {
      if (stk->s)
        free (stk->s);
      free (stk);
    }
}
/* STACK ROUTINES END */

Code Description

• int check_balanced_parenthesis (char *exp, int *error_at) : Accepts an expression exp to check for balanced parenthesis, other symbols are ignored. The error_at will store the position where the first error was encountered. If NULL is passed in error_at, it will not be considered. In case of an error a nonzero values is returned, in case of a correct expression a 0 is returned.
  The stack is first allocated. The while loop in this main function takes each character from the input string and pushes it on the stack if it is an opening bracket ‘(‘ or ‘{‘ or ‘[‘ . If it is a closing bracket ‘)’ or ‘}’ or ‘]’ it pops the top symbol and matches if the popped symbol is the matching of the current closing bracket, if yes then a match is found and the process continues by scanning the next symbol. Else if a mismatch is the matching is found then it sets error to TRUE and breaks from the loop. If stack is empty that there is no matching bracket in the stack, and the process sets error to TRUE and breaks from the while loop. When the input string has ended, it checks if there are still some brackets/parenthesis to be matched in the stack by invoking stack_is_empty() function. If the stack is not empty then there are unmatched brackets/parenthesis and sets error to TRUE. At last the error variable is tested. It is is TRUE then an error occurred, then the entered string is unbalanced. Because as soon as the error was detected the process broke from the loop setting error to true, so the current value of variable i will point to the location of the first error. If the error_at variable is supplied with the function call then this error location is assigned to it. If error is FALSE then no error had occurred thus the initial value of error is unchanged, so the input string is balanced. The stack is destroyed and the value of error is returned. Note that any other symbol in the input string other than the parenthesis symbols are ignored by the routine, and it only checks if the organization of the parenthesis are correct.

• int main (void) : The main function drives the check_balanced_parenthesis () function. It takes an input string from the user and calls the check_balanced_parenthesis () function. It also passes a variable address to get the error position value. Then it checks for the return value and appropriately prints messages and error location (if any).

• The stack functions are described in brief. The stack type has the following structure:

  typedef struct { 
      char *s;
      int top; 
  } stack;
  

  The stack functions are as following:

  • void stack_push (stack * stk, char token) : Pushes a token in the stack
  • int stack_pop (stack * stk) : Pops out the top most token from the stack
  • int stack_is_empty (stack * stk) : Checks if the stack is empty, if it is empty then returns TRUE else returns FALSE
  • stack * stack_create (int n) : Allocates stack space of size n bytes and initialize the stack top pointer, and returns the allocated stack.
  • void stack_delete (stack *stk) : Deletes an allocated stack stk

Output

Some sample runs are shown below:

Run 1: input = [{()[{()}]}({})]

Enter parenthesized string : [{()[{()}]}({})]
Parenthesis are BALANCED
[/souorcecode]

<em>Run 2: input = {a+(b*c)+[d*e/{f^g}]/22} </em>

Enter parenthesized string : {a+(b*c)+[d*e/{f^g}]/22} 
Parenthesis are BALANCED 

Run 3: input = {a+(b*c+[d*e/{f^g}]/22}

Enter paranthesized string : {a+(b*c+[d*e/{f^g}]/22} 
Parenthesis are UNBALANCED. 
First Error at location 23

Run 4: input = ((()}

Enter paranthesized string : ((()}
Parenthesis are UNBALANCED. 
First Error at location 5

Comments

This function can be used to test if an entered equation has balanced parenthesis as a part of a stack based algebraic expression parser, with some modifications as per need.