Problem Statement -
Given an expression string composed with 2 characters '(' and ')', write a program to examine whether the given string of parenthesis are balanced or not?
Solution-
While scanning the string left to right one character to another only 2 possible characters '(' and ')' will be encountered.
We will try to understand it by below example:
1. If symbol is '(' is found, it must be stored somewhere.
2. If symbol ')' is found, the last tracked symbol '(' must be removed from processing storage.
When we concentrate on above conditions carefully, we can easily decide we need a data structure which will store '(' symbols but processing will only be at last inserted symbol. And such functionality is available in Stack data structure. Below is the algorithm for above problem statement.
IsValidParentesisPair(str)
1. Create a stack S
2. for all character from i=1 to str.length() in str.
3. ch=str[i]
4. if ch=='('
5. S.push(ch)
6. if ch ==')'
7. if S is empty
8. return false;
9. if S.peek()=='('
10. S.pop()
11. If S.size()==0
12. return true
13 return false
JAVA code for above problem:
// Online Java Compiler
// Use this editor to write, compile and run your Java code online
import java.util.*;
import java.io.*;
class HelloWorld {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Please enter string");
String str=br.readLine();
boolean result=isBalancedParenthesis(str);
System.out.println("Balanced parenthesis check is :"+result);
}
private static boolean isBalancedParenthesis(String str)
{
Stack<Character> stack=new Stack<>();
for(int i=0;i<str.length();i++)
{
char ch=str.charAt(i);
if(ch=='(')
{
stack.push(ch);
}
if(ch==')')
{
if(stack.isEmpty())
{
return false;
}
else
{
stack.pop();
}
}
}
return stack.isEmpty();
}
}
