C program to Check for balanced Parentheses in an Expression using Stack

• Write a program in C to Check if Expression is correctly Parenthesized.

Given a string of '{' and '}' parentheses characters, we have to check whether parentheses are in correct order or not.

Valid Expressions
{}{}{}{{}}, {{{{}}}{}}, {{{{}}}}
Invalid Parenthesis Expressions 
{{{}{}{{{, }}{{}{{}, {{{{{{{{, }}}}{{{{

• Number of opening parenthesis('{') must be same as number of closing parenthesis('}').
• For every '}', there must be a corresponding '{' before.
• At any moment of time number of '{' must be >= number of '}'.

Algorithm to check balanced parenthesis

• Initialize a character stack. Set top pointer of stack to -1.
• Find length of input string using strlen function and store it in an integer variable "length".
• Using a for loop, traverse input string from index 0 to length-1.
  • If current character is '{', then push it inside stack.
  • If current character is '}', then pop a character from stack. If stack is empty, then input string is invalid, it means there is no matching opening parenthesis corresponding to closing parenthesis.
• After complete traversal of input string, If stack is empty then input expression is a Valid expression otherwise Invalid.

---

C program to check if Expression is correctly Parenthesized

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

#define MAXSIZE 100
#define TRUE 1
#define FALSE 0 

// Structure defining Stack data structure
struct Stack {
    int top;
    int array[MAXSIZE];
} st;

/*
Initializes the top index to -1
*/
void initialize() {
 st.top = -1;
}

/*
 Checks if Stack is Full or not 
*/
int isFull() {   
    if(st.top >= MAXSIZE-1)
        return TRUE;
    else 
        return FALSE;
}

/*
 Checks if Stack is Empty or not
*/
int isEmpty() {
 if(st.top == -1)
     return TRUE;
 else 
     return FALSE;
}

/*
 Adds an element to stack and then increment top index 
*/
void push(int num) {
    if (isFull())
        printf("Stack is Full...\n");
    else {
        st.array[st.top + 1] = num;
        st.top++;
    }
}

/*
 Removes top element from stack and decrement top index
*/
int pop() {
    if (isEmpty())
        printf("Stack is Empty...\n");
    else {
     st.top = st.top - 1;
        return st.array[st.top+1];
    }
}

int main() {
    char inputString[100], c;
    int i, length;
    initialize();
    printf("Enter a string of paranthesis\n");
    gets(inputString);
    length = strlen(inputString);
    /*
    # for '{' : we push '{' in stack 
    # for '}' : we pop a character from stack. For every '}' there must be one '{' earlier.  
                This will ensure that
                ** There are equal number of '{' and '}' characters in string.
                ** For every '{' there is a '}' in input string later.   
            
    */
    for(i = 0; i < length; i++){
        if(inputString[i] == '{')
            push(inputString[i]);
        else if(inputString[i] == '}')
            pop();
        else {
            printf("Error : Invalid Character !! \n");
            return 0;
        }
    }
    
    if(isEmpty())
        printf("Valid Paranthesis Expression\n");
    else 
        printf("InValid Paranthesis Expression\n");
        
    return 0;
}

Output

Enter a string of paranthesis
{{{}{}{{}}{}}}
Valid Paranthesis Expression

Enter a string of paranthesis
{{{}{}{}}{}}}}}
InValid Paranthesis Expression