括号匹配、进制转换与堆栈

定义堆栈接口：

 

package stack;

public interface Stack {
	//返回堆栈的大小
	public int getSize();
	//判断堆栈是否为空
	public boolean isEmpty();
	//数据元素e入栈
	public void push(Object e);
	//栈顶元素出栈
	public Object pop()throws StackEmptyException;
	//取栈顶元素看看
	public Object peek()throws StackEmptyException;
}

 定义节点类型：

 

package stack;

public class SLNode {
	public SLNode next;
	public Object e;
	
	public SLNode(SLNode next,Object e)
	{
		this.next=next;
		this.e=e;
	}

}

 堆栈实现：

 

package stack;

public class StackSLinked implements Stack{
	private SLNode top;
	private int size;//标记栈的大小
	
	public StackSLinked()
	{
		top=null;size=0;
	}

	@Override
	public int getSize() {
		
		return size;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return size==0;
	}

	@Override
	public void push(Object e) {
		SLNode q=new SLNode(top,e);
		top=q;
		size++;
		
	}

	@Override
	public Object pop() throws StackEmptyException {
		if(size<1)
			throw new StackEmptyException("栈为空");
		Object obj=top.e;
		top=top.next;
		size--;
		return obj;
	}

	@Override
	public Object peek() throws StackEmptyException {
		if(size<1)
		{
			throw new StackEmptyException("栈为空");
			
		}
		
		return top.e;
	}

}

 堆栈异常定义：

 

package stack;

public class StackEmptyException extends Exception{
	
	public StackEmptyException(String exception)
	{
		super(exception);
		
	}

}

 

Client 包含括号匹配和进制转换算法：

 

package stack;

public class Client {
	public static void main(String[] args) {
		//baseConversion(8);
		System.out.println(bracketMatch("{[wf(wf)]}"));

	}

	// 进制转换算法
	public static void baseConversion(int val) {
		Stack s = new StackSLinked();
		while (val > 0) {
			s.push(val % 8 + "");
			val = val / 8;
		}
		while (!s.isEmpty())
			try {
				System.out.print((String) s.pop());
			} catch (StackEmptyException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
	}

	// 括号匹配算法
	public static boolean bracketMatch(String str) {
		Stack s = new StackSLinked();
		for (int i = 0; i < str.length(); i++) {
			char c = str.charAt(i);
			switch (c) {
			case '{':
			case '[':
			case '(':
				s.push(Integer.valueOf(c));
				break;
			case '}':
				try {
					if (!s.isEmpty() && ((Integer) s.pop()).intValue() == '{')
						break;
					else
						return false;
				} catch (StackEmptyException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			case ']':
				try {
					if (!s.isEmpty() && ((Integer) s.pop()).intValue() == '[')
						break;
					else
						return false;
				} catch (StackEmptyException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			case ')':
				try {
					if (!s.isEmpty() && ((Integer) s.pop()).intValue() == '(')
						break;
					else
						return false;
				} catch (StackEmptyException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}

			}

		}
		if (s.isEmpty())
			return true;
		else
			return false;

	}

}