parenthesismatching.java

国外的数据结构与算法分析用书

import dslib.dispenser.LinkedStackUos;

public class ParenthesisMatching
{
	public static void main(String[] args)
	{

		String testString = "{([()]{})[]}([])";
		if (match(testString))
			System.out.println("In " + testString + "parenthesis match.");
		else
			System.out.println("In " + testString + "parenthesis do NOT match.");
		
		testString = "[()[]{()]}";
		if (match(testString))
			System.out.println("In " + testString + "parenthesis match.");
		else
			System.out.println("In " + testString + "parenthesis do NOT match.");
		
	}
	
	/** Test the input string to determine whether its parentheses are properly nested.
		Analysis: Time = O(input.length()) */
	public static boolean match(String input)
	{

		LinkedStackUos s = new LinkedStackUos();
		for  (int index = 0; index < input.length(); index++)
		{
			if (input.charAt(index) =='(' | input.charAt(index) =='{' | input.charAt(index) =='[')
				s.insert(new Character(input.charAt(index)));
			else if (s.isEmpty())
				return false;
			else if (input.charAt(index) == ')' & ((Character)s.item()).charValue() == '(')
				s.deleteItem();
			else if (input.charAt(index) == '}' & ((Character)s.item()).charValue() == '{')
				s.deleteItem();
			else if (input.charAt(index) == ']' & ((Character)s.item()).charValue() == '[')
				s.deleteItem();
			else
				return false;
		}
		if (s.isEmpty())
			return true;
		else
			return false;
	}
}