Balanced Parenthesis

About

In programming ( and ) are called parenthesis and are commonly used in mathematical expressions like

3 + (6 / 2)

If total number of opening ( is equal to total number of closing ) then the expression is said to have balanced parenthesis.

3 cases of parenthesis

• no. of ( is equal to no. of )
• Extra no. of (
• Extra no. of )

Case 1 gives a balanced expression.
While case 2 and case 3 gives an unbalanced expression.

How to solve

We will use variable bf to measure balance factor. bf will tell whether the expression is balanced or not.

Initially set bf = 0

Scan the expression from left to right.

For each ( increment bf by 1
For each ) decrement bf by 1
Continue scanning as long as bf >= 0

After scanning is complete
If bf == 0 then we have a balanced expression
Else an unbalanced expression

Code in C

/*
 * balanced parenthesis
 */

#include <stdio.h>

int main(){
	//variables
	char expr[100];
	int bf = 0;	//balance factor
	int i;
	
	//input
	printf("Enter expression: ");
	scanf("%s", &expr);
	
	//scan
	i = 0;
	while(expr[i] != '\0'){
		if(expr[i] == '(')
			bf++;
		else if(expr[i] == ')'){
			bf--;
			if(bf < 0)
				break;	//terminate search
		}
		i++;
	}
	
	//output
	if(bf == 0)
		printf("Balanced parenthesis.\n");
	else
		printf("Unbalanced.\n");
	return 0;
}