/*
Description: 1) This program determines if a string input with
symbols such as () {} {} are properly nested.
*/
import java.util.EmptyStackException;
public class MartinStack
{
private char[ ] data;
private int manyItems;
public MartinStack( )
{
final int CAPACITY = 1000;
manyItems = 0;
data = new char[CAPACITY];
}
public boolean isEmpty( )
{
return (manyItems == 0);
}
public char peek( )
{
if (manyItems == 0)
throw new EmptyStackException( );
return data[manyItems-1];
}
public char pop( )
{
if (manyItems == 0)
throw new EmptyStackException( );
return data[--manyItems];
}
public void push(char item)
{
data[manyItems] = item;
manyItems++;
}
public int size( )
{
return manyItems;
}
}
/*
A:\>javac Balanced.java
A:\>java Balanced
Enter a string containing various kinds
of parentheses ( ) { } [ ]. I'll check whether
the parentheses are balanced.
Your string: THISI=(0)
That is balanced.
Would you like to input another string? [Y or N] Y
Your string: (){}[
That is not balanced.
Would you like to input another string? [Y or N] N
Have a good day!
A:\>java Balanced
Enter a string containing various kinds
of parentheses ( ) { } [ ]. I'll check whether
the parentheses are balanced.
Your string: {(3 + 2)/ (5 - 2) * 56}
That is balanced.
Would you like to input another string? [Y or N] y
Your string: {(3 + 2) / (5 - 2 * 56}
That is not balanced.
Would you like to input another string? [Y or N] y
Your string: This is a test( )
That is balanced.
Would you like to input another string? [Y or N] y
Your string: This is () a test {} [
That is not balanced.
Would you like to input another string? [Y or N]
*/
/*___________________________*/
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PushbackReader;
import MartinStack;
public class Balanced extends PushbackReader
{
final static int EOF_VALUE = -1;
final static char ZERO_CHAR = '\0';
private boolean formatProblem = false;
public Balanced(InputStream in)
{
super(new InputStreamReader(in));
}
public Balanced(InputStreamReader isr)
{
super(isr);
}
public char charInput( )
{
readSpaces( );
return readChar( );
}
public char charInputLine( )
{
char answer = charInput( );
skipLine( );
return answer;
}
public char charQuery(String prompt)
{
char answer;
System.out.print(prompt);
return charInputLine( );
}
public double doubleInput( )
{
final char POINT = '.';
StringBuffer input = new StringBuffer( );
readSpaces( );
input.append(readSign( ));
input.append(readDigits( ));
if (peek( ) == POINT)
{
input.append(readChar( ));
input.append(readDigits( ));
}
if (Character.toUpperCase(peek( )) == 'E')
{
input.append(readChar( ));
input.append(readSign( ));
input.append(readDigits( ));
}
try
{
formatProblem = false;
return Double.valueOf(input.toString( )).doubleValue( );
}
catch (NumberFormatException e)
{
formatProblem = true;
return Double.NaN;
}
}
public double doubleInputLine( )
{
double answer = doubleInput( );
skipLine( );
return answer;
}
public double doubleQuery(String prompt)
{
double answer;
System.out.print(prompt);
answer = doubleInputLine( );
while (formatProblem)
{
System.out.print("Invalid response. Please type a double value: ");
if (isEOF( ))
return Double.NaN;
answer = doubleInputLine( );
}
return answer;
}
private static void handleException(Exception e)
{
System.err.println("Exception:" + e);
System.err.println("Balanced program will cause program to halt.");
System.exit(0);
}
public void ignore( )
{
readChar( );
}
public int intInput( )
{
String input = null;
readSpaces( );
input = readSign( ) + readDigits( );
try
{
formatProblem = false;
return Integer.parseInt(input);
}
catch (NumberFormatException e)
{
formatProblem = true;
return Integer.MIN_VALUE;
}
}
public int intInputLine( )
{
int answer = intInput( );
skipLine( );
return answer;
}
public int intQuery(String prompt)
{
int answer;
System.out.print(prompt);
answer = intInputLine( );
while (formatProblem)
{
System.out.print("Invalid response. Please type an integer value: ");
if (isEOF( ))
return Integer.MIN_VALUE;
answer = intInputLine( );
}
return answer;
}
public boolean isEOF( )
{
return (readAhead( ) == EOF_VALUE);
}
public boolean isEOLN( )
{
int next = readAhead( );
return (next == '\n') || (next == '\r') || (next == EOF_VALUE);
}
public boolean isFormatProblem( )
{
return formatProblem;
}
public char peek( )
{
int next = readAhead( );
if (next == EOF_VALUE)
return ZERO_CHAR;
else
return (char) next;
}
public boolean query(String prompt)
{
String answer;
System.out.print(prompt + " [Y or N] ");
answer = stringInputLine( ).toUpperCase( );
while (!answer.startsWith("Y") && !answer.startsWith("N"))
{
System.out.print("Invalid response. Please type Y or N: ");
if (isEOF( ))
return false;
answer = stringInputLine( ).toUpperCase( );
}
return answer.startsWith("Y");
}
private int readAhead( )
{
int next = EOF_VALUE;
try
{
next = read( );
if (next == EOF_VALUE)
{
//pause(1000);
}
else
unread(next);
}
catch (IOException e)
{
handleException(e);
}
return next;
}
private char readChar( )
{
int next = EOF_VALUE;
try
{
next = read( );
if (next == EOF_VALUE)
{
next = ZERO_CHAR;
}
}
catch (IOException e)
{
handleException(e);
}
return (char) next;
}
private String readDigits( )
{
StringBuffer buffer = new StringBuffer( );
while (Character.isDigit(peek( )))
buffer.append(readChar( ));
return buffer.toString( );
}
private String readSign( )
{
StringBuffer buffer = new StringBuffer(1);
char possibleSign;
possibleSign = peek( );
if ((possibleSign == '-') || (possibleSign == '+'))
buffer.append(readChar( ));
return buffer.toString( );
}
private String readSpaces( )
{
StringBuffer buffer = new StringBuffer( );
while (Character.isWhitespace(peek( )))
buffer.append(readChar( ));
return buffer.toString( );
}
public void skipLine( )
{
while (!isEOLN( ))
readChar( );
if (peek( ) == '\r')
readChar( );
if (peek( ) == '\n')
readChar( );
}
public String stringInput( )
{
StringBuffer buffer = new StringBuffer( );
formatProblem = false;
readSpaces( );
while (!isEOF( ) && !Character.isWhitespace(peek( )))
buffer.append(readChar( ));
return buffer.toString( );
}
public String stringInputLine( )
{
StringBuffer buffer = new StringBuffer( );
while (!isEOLN( ) && !isEOF( ))
buffer.append(readChar( ));
skipLine( );
return buffer.toString( );
}
public String stringQuery(String prompt)
{
System.out.print(prompt);
return stringInputLine( );
}
public static void main(String[ ] args)
{ Balanced stdin = new Balanced(System.in);
String expression;
System.out.println("Enter a string containing various kinds");
System.out.println("of parentheses ( ) { } [ ]. I'll check whether");
System.out.println("the parentheses are balanced.");
do
{
expression = stdin.stringQuery("Your string: ");
if (isBalanced(expression))
System.out.println("That is balanced.");
else
System.out.println("That is not balanced.");
}
while (stdin.query("Would you like to input another string?"));
System.out.println("Have a good day!");
}
public static boolean isBalanced(String expression)
{
final char LEFT_PARENTHE = '(';
final char RIGHT_PARENTHE = ')';
final char LEFT_BRACE = '{';
final char RIGHT_BRACE = '}';
final char LEFT_BRACKET = '[';
final char RIGHT_BRACKET = ']';
MartinStack store = new MartinStack( ); // store left parentheses
int i; // Index into the string
boolean failed = false; // mismatch
for (i = 0; !failed && (i < expression.length( )); i++)
{
switch (expression.charAt(i))
{
case LEFT_PARENTHE:
case LEFT_BRACE:
case LEFT_BRACKET:
store.push(expression.charAt(i));
break;
case RIGHT_PARENTHE:
if (store.isEmpty( ) || (store.pop( ) != LEFT_PARENTHE))
failed = true;
break;
case RIGHT_BRACE:
if (store.isEmpty( ) || (store.pop( ) != LEFT_BRACE))
failed = true;
break;
case RIGHT_BRACKET:
if (store.isEmpty( ) || (store.pop( ) != LEFT_BRACKET))
failed = true;
break;
}
}
return (store.isEmpty( ) && !failed);
}
}