Checking Balance of Symbols in a expression

This article is part of article series - "Datastructures"

A balanced expression contains right number of closing and open braces.

For example:

• [[ - unbalanced expression
• []{}() - balanced expression
• [(*)] - balanced expression

Let us see how to find if an expression is balanced or not by checking for following operators [ ] { } and ( ) in the given expression.

Using Stacks

Pseudocode:

We divide [ , ] , { , } , ( , ) operators into LEFT and RIGHT sets where LEFT set contains ( , { ,  [ operators while RIGHT set contains ) , } , ] operators. So we have a one to one mapping between RIGHT and LEFT set operators i,e

• { --- }
• [ ---] 
• ( --- )

NOTE: Stack related operations like create stack, delete stack, push into stack and pop from stack are considered generic and we are not including its logic in below pseudocode.

********************************************************
 Function  : isExprBalanced 

 Calls     : popFromStack 

 Called by : main

 Input 
 Parameters: stack, var
  
 Returns   : balanced : TRUE 
             unbalanced: FALSE
********************************************************

CASE var

  ')' : IF stackTop equals '(' THEN
          CALL popFromStack (stack)
          RETURN TRUE
        ENDIF

  '}' : IF stackTop equals '{' THEN
          CALL popFromStack (stack)
          RETURN TRUE
        ENDIF

  ']' : IF stackTop equals '[' THEN
          CALL popFromStack (stack)
          RETURN TRUE
        ENDIF
  
ENDCASE

RETURN FALSE

********************************************************
 Function  : main

 Calls     : createStack
             isExprBalanced              
             pushIntoStack 
             popFromStack 

 Called by : NONE 

 Input 
 Parameters: Accepts input expression for processing
  
 Returns   : If input expression is balanced or not.
********************************************************

SET i to 0
GET input expression from user into input[20]
SET var with input[i]

CALL createStack

WHILE var != end of string

  IF var belongs to (RIGHT set) THEN

    CALL isExprBalanced (stack,var)

    IF not balanced THEN
      PRINT expression is not balanced
      RETURN
    ENDIF 

  ELSE IF var belongs to (LEFT set) THEN

    CALL pushIntoStack (stack,var)

  ENDIF

  SET var with input[INCREMENT i]

ENDWHILE

IF stack is empty THEN
  PRINT expression is balanced
ELSE
  PRINT expression is un-balanced
ENDIF

CALL freeStack (stack)

Complexity:

• TIme Complexity: O(n)
• Space Complexity: O(n)

Sample Code:

stackSLL.h

#define MAX_STACK_SIZE 10
#define RESULT_ERROR -1
#define RESULT_OK     0

struct sllNode
{
  struct sllNode *next;
  int data;
};

struct sllHead
{
  struct sllNode *next;
  u_int32_t count;
  u_int32_t maxStackSize;
};

#define IS_RIGHT(_i)  ((_i == ')') || (_i == '}') || (_i == ']'))

#define IS_LEFT(_i)  ((_i == '(') || (_i == '{') || (_i == '['))

stackSLL.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stackSLL.h"

/*Poping from a Stack*/
int
popFromStack(struct sllHead *head)
{
  struct sllNode *tmpNode_ptr = NULL;

  if (!head)
  {
    return RESULT_ERROR;
  }

  if (head->next)
  {
    tmpNode_ptr = head->next;
    head->next = head->next->next;
    free(tmpNode_ptr);
    head->count--;
  }    
  else  
    printf("Stack is Empty\n");

  return RESULT_OK;
} 

/*Pushing into Stack*/
int
pushIntoStack(struct sllHead *head, int data)
{
  struct sllNode *tmpNode_ptr = NULL;

  if (!head)
  {
    return RESULT_ERROR;
  }

  if (head->count == head->maxStackSize)
  {
    printf ("Stack is FILLED to MAX level\n");
    return RESULT_ERROR;
  }

  tmpNode_ptr = (struct sllNode *)calloc(1, sizeof(struct sllNode));

  if (tmpNode_ptr)
    tmpNode_ptr->data = data;
  else
  {
    printf("Memory Allocation Failedn");
    return RESULT_ERROR;
  }

  tmpNode_ptr->next = head->next;
  head->next = tmpNode_ptr;
  head->count++;

  return RESULT_OK;
}

struct sllHead *
createStack()
{
  struct sllHead *head = struct sllHead *)calloc(1, sizeof(struct sllHead));

  if (head)
    head->maxStackSize = MAX_STACK_SIZE;

  return head;
}

void
freeStack(struct sllHead **head)
{
  if (*head)
  {
    while((*head)->count)
      popFromStack(*head);

    free(*head);
    *head = NULL;
  }
}

int
isExprBalanced (struct sllHead *head, char val)
{
  if (head == NULL || head->next == NULL)
    return RESULT_ERROR;

  if (!IS_RIGHT(val))
    return RESULT_ERROR;

  switch(val)
  {
    case ')':
      if (head->next->data == '(')
      {
        popFromStack(head);
        return RESULT_OK;
      }
    break;

    case '}':
      if (head->next->data == '{')
      {
        popFromStack(head);
        return RESULT_OK;
      }
    break;

    case ']':
      if (head->next->data == '[')
      {
        popFromStack(head);
        return RESULT_OK;
      }
    break;
  }

  return RESULT_ERROR;
}

int
main(int argc, char *argv[])
{
  char in[20];
  short i = 0;
  struct sllHead *stack = NULL;

  memset(in, 0, 20);

  printf("Enter expression containing ( { [ ) { ]: ");
  scanf("%s", in);

  stack = createStack();

  while(i < 20 && in[i] != '\0')
  {
    if (IS_RIGHT(in[i]))
    {
      if (isExprBalanced(stack, in[i]) != RESULT_OK)
      {
        printf("Expression is not balanced\n");
        goto EXIT;
      }
    }
    else if (IS_LEFT(in[i]))
    {
      if (pushIntoStack(stack, in[i]) == RESULT_ERROR)
        goto EXIT;
    }

  if (stack->count)
    printf ("Expression is not balanced\n");
  else
    printf ("Expression is balanced\n");

EXIT:

  freeStack (&stack);

  return RESULT_OK;
}