//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//Parentheses Checker
//Description: A class that checks whether an expression has properly
//	balanced parentheses using a stack.
//CS 284
//Programmed by Jonathan Voris
//2/27/06
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
import java.util.Stack;

class ParenChecker
{

	public static boolean isOpenParen(char ch)
	{
		if ((ch == '(') || (ch == '{') || (ch == '['))
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	public static boolean isCloseParen(char ch)
	{
		if ((ch == ')') || (ch == '}') || (ch == ']'))
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	//If given an open parenthesis, closingMatch returns the
	//corresponding closing parenthesis. Othereise, it returns
	//a space.
	public static char closingMatch(char openParen)
	{
		if (openParen == '(')
		{
			return ')';
		}
		else if (openParen == '[')
		{
			return ']';
		}
		else if (openParen == '{')
		{
			return '}';
		}
		else
		{
			return ' ';
		}
	}

	//isBalanced is the central ParenChecker method. it accepts
	//an expression string and returns true if its parentheses
	//are balanced and false otherwise. This is based on the
	//pseudocode given in Chapter 5, slide 10 of the CS284
	//lecture notes.
	public static boolean isBalanced(String expression)
	{
		Stack parenStack = new Stack();
		//assume the expression is balanced - expressions
		//without parentheses are vacuously balanced
		boolean isBalanced = true;
		int expIndex = 0;

		while (isBalanced && (expIndex < expression.length()))
		{//continue looping over the expression while we're
		 //not at its end and the expression is balanced so far

		 	//grab the character at the current spot in the expression
			char curChar = expression.charAt(expIndex);

			if (isOpenParen(curChar))
			{//if the current character is an open parenthesis,
			 //add it to the stack
				parenStack.push(curChar);
			}
			else if (isCloseParen(curChar))
			{//if the current character is a close parenthesis...
				if (!parenStack.empty())
				{
					char lastOpenParen = (Character)parenStack.pop();
					if (curChar != closingMatch(lastOpenParen))
					{//...and it doesn't match the last open parenthesis
					 //encountered, the expression is unbalanced.
						isBalanced = false;
					}
					//...and it does match the last open parenthesis,
					//the expression is balanced so far
				}
				else
				{//...and no corresponding open parenthesis has been added
				 //to the stack, the expression is unbalanced
					isBalanced = false;
				}
			}
		//don't forget to increment our position in the expression
		expIndex++;
		}

		if (isBalanced && parenStack.empty())
		{//if there is nothing left on the stack and no imbalances were detected,
		 //the expression is balanced
			return true;
		}
		else
		{//Either an imbalance was detected or there are still open parentheses
		 //on the stack, meaning they did not have a corresponding close parenthesis.
		 //Both cases mean the expression is not balanced.
			return false;
		}

	}

	//main is full of "driver program" tests
	public static void main(String[] args)
	{
		String parenTest = "{[(a)]}";
		System.out.println("Open Paren Tests");
		for (int x = 0; x < parenTest.length(); x++)
		{
			System.out.println(parenTest.charAt(x) + " : " + isOpenParen(parenTest.charAt(x)));
		}

		System.out.println("Close Paren Tests");
		for (int x = 0; x < parenTest.length(); x++)
		{
			System.out.println(parenTest.charAt(x) + " : " + isCloseParen(parenTest.charAt(x)));
		}

		System.out.println("Closing Match Tests");
		for (int x = 0; x < parenTest.length(); x++)
		{
			System.out.println(parenTest.charAt(x) + " : " + closingMatch(parenTest.charAt(x)));
		}

		System.out.println("Balanced Tests");
		System.out.println(parenTest + " : " + isBalanced(parenTest));
		System.out.println("{spam}*(eggs/(foo^2)) : " + isBalanced("{spam}*(eggs/(foo^2))"));
		System.out.println("{(this)almost[matches]}] : " + isBalanced("{(this)almost[matches]}]"));
		System.out.println("definately not] : " + isBalanced("definately not]"));
		System.out.println("Does this? : " + isBalanced("Does this?"));
		System.out.println("{what about (this}?) : " + isBalanced("{what about (this}?)"));
	}
}