Balanced Parenthesis Checker | Program to check for balanced parenthesis in an expression

Program to check for balanced parenthesis with and without using stack is discussed here. You can develop a parenthesis checker without using stack as well. But using stack can have several advantages.

  • Using a stack to balance parenthesis will help you balance different types of grouping operators such as []{} and () and verify that they are correctly nested.
  • Using a stack will also help improve the efficiency of the code

Example:

Input : ((()))
Output: 1

Input : ()((
Output : -1

Balanced Parenthesis Checker using Stack

The algorithm to check for balanced parenthesis with a stack is given below.

  • When any open symbol i.e, ‘(‘, ‘{‘, ‘[‘ is encountered, it will be pushed in the stack.
  • If any close symbol i.e, ‘)’, ‘}’, ‘]’ is encountered, any of the three can happen
  • The TOS (Top Of Stack) is checked, if the encountered close symbol matches with its open symbol, then open symbol which is at TOS is popped out.                        (OR)
  • The TOS (Top Of Stack) is checked, if the encountered close symbol does not match with its open symbol, then “-1” is returned as there is no matching symbol.                 (OR)
  • The TOS (Top Of Stack) is checked,if the stack is empty, then “-1” is returned as there is no open symbol in the stack.

balanced parenthesis checker

Program:

// C code to check balanced parenthesis

#include
#include
char st[20];
int top=-1;
void psh(char);
char pop();
int main()
{
char a[20],t;
int i,f=1;
scanf(“%s”,a);
for(i=0;i<strlen(a);i++)
{
if(a[i]=='(‘||a[i]=='{‘||a[i]=='[‘)
psh(a[i]);
if(a[i]==’)’||a[i]==’}’||a[i]==’]’)
{
if(top==-1)
f=0;
else
{t=pop();
if(a[i]==’)’&&(t=='[‘||t=='{‘))
f=0;
if(a[i]==’}’&&(t=='(‘||t=='[‘))
f=0;
if(a[i]==’]’&&(t=='{‘||t=='(‘))
f=0;
}
}
}
if(top>=0)
f=0;
if(f==0)
printf(“Unbalanced\n”);
else
printf(“Balanced\n”);
return 0;
}
void psh(char a)
{
st[++top]=a;
}
char pop()
{
return st[top–];
}

// C++ code to check balanced parenthesis

#include
#include //to use strlen(), we need to include this header
using namespace std;
char st[20];
int top=-1;

void push(char a)
{
st[++top]=a;
}
char pop()
{
return st[top–];
}

int main()
{
char a[20],t;
int i,f=1;
cout<<“Enter the String: “;
cin>>a;
for(i=0;i<strlen(a);i++)
{
if(a[i]=='(‘ || a[i]=='{‘ || a[i]=='[‘)
push(a[i]);
if(a[i]==’)’ || a[i]==’}’ ||a[i]==’]’)
{
if(top==-1)
f=0;
else
{
t=pop();
if(a[i]==’)’ && (t=='[‘ || t=='{‘))
f=0;
if(a[i]==’}’ && (t=='(‘ || t=='[‘))
f=0;
if(a[i]==’]’ && (t=='{‘ || t=='(‘))
f=0;
}
}
}
if(top>=0)
f=0;
if(f==0)
cout<<“Unbalanced”;
else
cout<<“Balanced”;
return 0;
}

// Java code to check balanced parenthesis

import java.util.Stack;

public class Main
{
public static boolean balParenthesis(String exp)
{
Stack stack = new Stack();

for (int i = 0; i < exp.length(); i++)
{
if (exp.charAt(i) == ‘(‘ || exp.charAt(i) == ‘{‘ ||
exp.charAt(i) == ‘[‘) {
stack.push(exp.charAt(i));
}

if (exp.charAt(i) == ‘)’ || exp.charAt(i) == ‘}’ ||
exp.charAt(i) == ‘]’)
{
if (stack.empty()) {
return false;
}

Character top = stack.pop();

if ((top == ‘(‘ && exp.charAt(i) != ‘)’) ||
(top == ‘{‘ && exp.charAt(i) != ‘}’) ||
(top == ‘[‘ && exp.charAt(i) != ‘]’)) {

return false;
}
}
}

return stack.empty();
}

public static void main(String[] args)
{
String exp = “{()}[{}]”;

if (balParenthesis(exp)) {
System.out.println(“The expression is balanced”);
} else {
System.out.println(“The expression is not balanced”);
}
}
}

 

# Python code to check balanced parenthesis

class Stack:
def __init__(self):
self.items = []

def is_empty(self):
return self.items == []

def push(self, data):
self.items.append(data)

def pop(self):
return self.items.pop()

s = Stack()
exp = input(‘Please enter the expression: ‘)

for c in exp:
if c == ‘(‘:
s.push(1)
elif c == ‘)’:
if s.is_empty():
is_balanced = False
break
s.pop()
else:
if s.is_empty():
is_balanced = True
else:
is_balanced = False

if is_balanced:
print(‘Balanced’)
else:
print(‘Unbalanced’)

Balanced Parenthesis Checker without using Stack

The algorithm to check for balanced parenthesis with a stack is given below.

  • Input the expression to be checked.
  • Use a temporary variable say count to keep track of number of opening braces in the expression.
  • Search for closing parenthesis for the corresponding opening parenthesis in the expression.
  • If the count of closing and opening parenthesis are the same, then the expression is said to be balanced.

Program:

// C++ code to check if an expression contains balanced parenthesis  or not

#include <bits/stdc++.h>
using namespace std;

char check(char c)
{
if (c == ‘(‘)
return ‘)’;
if (c == ‘{‘)
return ‘}’;
if (c == ‘[‘)
return ‘]’;
return -1;
}

bool check(char expression[], int n)
{
if (n == 0)
return true;
if (n == 1)
return false;
if (expression[0] == ‘)’ || expression[0] == ‘}’ || expression[0] == ‘]’)
return false;

char closing = check(expression[0]);

int i, count = 0;
for (i = 1; i < n; i++) {
if (expression[i] == expression[0])
count++;
if (expression[i] == closing) {
if (count == 0)
break;
count–;
}
}

if (i == n)
return false;

if (i == 1)
return check(expression + 2, n – 2);

return check(expression + 1, i – 1) && check(expression + i + 1, n – i – 1);
}

int main()
{
char expression[15];
cout << “\nEnter the expression : “;
cin >> expression;
int n = strlen(expression);
if (check(expression, n))
cout << “Balanced”;
else
cout << “Not Balanced”;
return 0;