Wellformed Parenthesis problem Write a Java program that det

Well-formed Parenthesis problem: Write a Java program that determines whether a given line of input has a balanced set of parentheses or not. The input String will only contain left and right parentheses and perhaps blank spaces.   If the input string has blank spaces, you can ignore them and look only for left or right parenthesis. Use the Stack data structure (as given in the java.util.* library) to solve the problem. What is the time-complexity of the algorithm underlying your program?

Here is the definition of balanced parentheses:

As you move from left to right through the input string, you should never encounter more right parentheses than left parentheses.

The total number of left parentheses must equal the total number of right parentheses.

You can either assume that the string is read in from the keyboard or hard-coded within the main () of your program. Here are some sample inputs and program outputs to help you understand the problem.

1. ((()) – Not balanced

2. ())(() – Not balanced

3. (()())) – Not balanced

4. (())() –   Balanced

Solution

Please find the required solution:

import java.util.Stack;

public class BalanceChecker {

/**
* Sample test cases run using main method
*
* @param args
*/
public static void main( String[] args )
{
System.out.println(\"((()) is \" + (isBalanced(\"((())\") ? \"Balanced\" : \"Not Balanced\"));
System.out.println(\"())(() is \" + (isBalanced(\"())(()\") ? \"Balanced\" : \"Not Balanced\"));
System.out.println(\"(()())) is \" + (isBalanced(\"(()()))\") ? \"Balanced\" : \"Not Balanced\"));
System.out.println(\"(())() is \" + (isBalanced(\"(())()\") ? \"Balanced\" : \"Not Balanced\"));
}

public static Boolean isBalanced( String input )
{
//Declaration of input stack of character
Stack<Character> inputStack = new Stack<Character>();

//iterate through each character of array
for( char atIndex : input.toCharArray() )
{
char temp;

// if index at \'(\' push to stack
if( atIndex == \'(\' )
inputStack.push(\'(\');

// if index at pop from stack and check if it balanced(that is \'(\')
else if( atIndex == \')\' )
{
if( inputStack.isEmpty() )
return false;
temp = inputStack.pop();
if( temp != \'(\' )
return false;
}
else
return false;
}

/**
* Upon iteration stack should be empty
*/
if( inputStack.isEmpty() )
return true;
else
return false;
}
}

Sample Result: