This problem is intended to better understand the use of the Stack class. Design a counting algorithm that checks an expression only for balanced parentheses (not curly or square brackets) without using an array or stack. Hint: count the parenthesis level using an integer that increases or decreases. Please follow the instructions and answer all the questions!

a. Write a program with a method isBalanced() that receives an expression as a String and returns true or false using this new counting algorithm. Write out the sample output from your main() method. It should get an expression and print a result similar to IsBalancedDemonstration.java (given below), except that you will not include curly or square brackets.

b. What is the Big-O time complexity of the algorithm in IsBalancedDemonstration.java that uses Stack? Briefly explain your answer.

c. What is the Big-O time complexity of this new counting algorithm? Briefly explain your answer.

d. Can this counting algorithm be used to evaluate expressions with all three kinds of parentheses and brackets, including curly and square, without using an array or stack? Explain why or why not in 2 3 sentences. NOTE: You do not need to write a program for this part.

IsBalancedDemonstration.java:

// This small demonstration program showing the isBalanced method, which uses

// a stack of characters to determine whether a string has balanced

// parentheses.

import java.util.Stack;

import java.util.Scanner;

public class IsBalancedDemonstration

{

public static void main(String[ ] args)

{

Scanner stdin = new Scanner(System.in);

String expression;

System.out.println("Please type a string containing various kinds");

System.out.println("of parentheses ( ) { } [ ]. I'll check whether");

System.out.println("the parentheses are balanced.");

do

{

System.out.print("Your string: ");

expression = stdin.nextLine( );

if (isBalanced(expression))

System.out.println("That is balanced.");

else

System.out.println("That is not balanced.");

}

while (query(stdin, "Another string?"));

System.out.println("Thanks for that balancing act.");

}

public static boolean query(Scanner input, String prompt)

{

String answer;

System.out.print(prompt + " [Y or N]: ");

answer = input.nextLine( ).toUpperCase( );

while (!answer.startsWith("Y") && !answer.startsWith("N"))

{

System.out.print("Invalid response. Please type Y or N: ");

answer = input.nextLine( ).toUpperCase( );

}

return answer.startsWith("Y");

}

public static boolean isBalanced(String expression)

// Postcondition: A true return value indicates that the parentheses in the

// given expression are balanced. Otherwise the return value is false.

// Note that characters other than ( ) { } and [ ] are ignored.

{

// Meaningful names for characters

final char LEFT_NORMAL = '(';

final char RIGHT_NORMAL = ')';

final char LEFT_CURLY = '{';

final char RIGHT_CURLY = '}';

final char LEFT_SQUARE = '[';

final char RIGHT_SQUARE = ']';

Stack store = new Stack( ); // Stores parens

int i; // An index into the string

boolean failed = false; // Change to true for a mismatch

for (i = 0; !failed && (i < expression.length( )); i++)

{

switch (expression.charAt(i))

{

case LEFT_NORMAL:

case LEFT_CURLY:

case LEFT_SQUARE:

store.push(expression.charAt(i));

break;

case RIGHT_NORMAL:

if (store.isEmpty( ) || (store.pop( ) != LEFT_NORMAL))

failed = true;

break;

case RIGHT_CURLY:

if (store.isEmpty( ) || (store.pop( ) != LEFT_CURLY))

failed = true;

break;

case RIGHT_SQUARE:

if (store.isEmpty( ) || (store.pop( ) != LEFT_SQUARE))

failed = true;

break;

}

}

return (store.isEmpty( ) && !failed);

}

}