Java实现的Stack和用Stack实现的BalanceChedker

废话不多少，直接上代码。
前面还有个Stack的实现和用Stack解析数学表达式。
http://blog.chinaunix.net/uid-7713641-id-5761516.html


这是Stack的实现，代码出自Object-Oriented Data Structures Using Java.

package Algorithms;

class StackUnderflowException extends RuntimeException{
    //only 2 constructor
    public StackUnderflowException(){
        super();
    }
    public StackUnderflowException(String message){
        super(message);
    }
}
class StackOverflowException extends RuntimeException{
    //only 2 constructor
    public StackOverflowException(){
        super();
    }
    public StackOverflowException(String message){
        super(message);
    }
}

interface StackInterface<T>{
    void push(T element) throws StackOverflowException;
    /* Throws StackOverflowException if this stack is full.
    otherwise places element at the top of this stack.
     */

    void pop() throws StackUnderflowException;
    //Throws StackUnderflowException if this stack is empty.
    //otherwise removes top element from this stack.

    T top() throws StackUnderflowException;
    //Throws StackUnderflowException if this stack is empty.
    //otherwise returns top element of this stack

    boolean isFull();
    //Returns true if this stack is full, otherwise returns false

    boolean isEmpty();
    //Returns true if this stack is empty, otherwise returns false.
}

class ArrayBoundedStack<T> implements StackInterface<T>{
    //use Array implement a stack
    protected final int DEFCAP = 100; //Default capacity
    protected T[] elements; //holds stack element
    protected int topIndex = -1; //index of top element in stack

    public ArrayBoundedStack(){
        elements = (T[]) new Object[DEFCAP];
    }

    public ArrayBoundedStack(int maxSize){
        elements = (T[]) new Object[maxSize];
    }

    public boolean isEmpty(){
        return (topIndex == -1);
    }

    public boolean isFull(){
        return (topIndex == (elements.length-1));
    }

    public void push(T element){
        if(isFull()){
            throw new StackOverflowException("Push attempted on a full stack");
        }else{
            topIndex++;
            elements[topIndex]=element;
        }
    }

    public void pop(){
        if(isEmpty()){
            throw new StackUnderflowException("Pop attempted on a empty stack");
        }else{
            elements[topIndex]=null;
            topIndex--;
        }
    }

    public T top() {
        T topOfStack = null;
        if (isEmpty()) {
            throw new StackUnderflowException("Top attempted on empty stack");
        } else {
            topOfStack = elements[topIndex];
            return topOfStack;
        }
    }
}

public class MyStack {

    public static void revStr(){
        ArrayBoundedStack<String> stringStack;
        stringStack = new ArrayBoundedStack<String>(3);
        stringStack.push("1 Hero: Demon Hunter");
        stringStack.push("2 Hero: Keeper of the Grove");
        stringStack.push("3 Hero: Priestess of the Moon");

        String line;
        System.out.println("Reverse");
        while(!stringStack.isEmpty()){
            line=stringStack.top();
            stringStack.pop();
            System.out.println(line);
        }
    }

    public static void main(String[] args) {
        revStr();
    }
}

下面是用Java的ArrayList实现的Stack。好简单啊

public class MyArrayListStack<T> implements StackInterface<T> {
    protected ArrayList<T> elements;
    public MyArrayListStack() {
        this.elements = new ArrayList<T>();
    }

    @Override
    public void push(T element){
        elements.add(element);
    }

    @Override
    public void pop() throws StackUnderflowException {
        if(isEmpty()){
            throw new StackUnderflowException("Pop attempted on a empty stack");
        }else{
            elements.remove(elements.size()-1);
        }
    }

    @Override
    public T top() throws StackUnderflowException {
        if(isEmpty()){
            throw new StackUnderflowException("Top attempted on a empty stack");
        }else{
            T topOfStack = elements.get(elements.size()-1);
            return topOfStack;
        }
    }

    @Override
    public boolean isFull() {
        //ArrayList is never full
        return false;
    }

    @Override
    public boolean isEmpty() {
        return elements.size() == 0 ;
    }
}

玩票性质的把LLNode写成了一个public 的InnerClass. 这是个单链表实现的Stack.

package Algorithms;

public class MyLinkedStack<T> implements StackInterface<T> {
    //Inner class LLNode
    public class LLNode<T>{
        private T info;
        private LLNode<T> link;

        public LLNode(T info) {
            this.info = info;
            this.link = null;
        }

        public void setInfo(T info){
            this.info = info;
        }

        public T getInfo() {
            return info;
        }

        public LLNode<T> getLink() {
            return link;
        }

        public void setLink(LLNode<T> link) {
            this.link = link;
        }
    }
    //reference to the top
    protected LLNode<T> top;

    public MyLinkedStack(){
        top=null;
    }

    public void push(T element){
        LLNode<T> newNode = new LLNode<T>(element);
        newNode.setLink(top);
        top = newNode;
    }

    public void pop(){
        if(isEmpty()){
            throw new StackUnderflowException("Pop attempted on an empty stack.");
        }else{
            top = top.getLink();
        }
    }

    public T top(){
        if(isEmpty()){
            throw new StackUnderflowException("Pop attempted on an empty stack.");
        }else {
            return top.getInfo();
        }
    }

    public boolean isFull(){
        //linked stack is never full
        return false;
    }

    public boolean isEmpty(){
        return (top == null);
    }
}

BalanceChecker类

package Algorithms;

public class BalanceChecker {

    protected String openSet;
    protected String closeSet;

    //constructor
    public BalanceChecker(String openSet, String closeSet) {
        //Preconditions: No character is contained more than once in the
        // combined openSet and closeSet strings.
        // The size of openSet = the size of closeSet.
        this.openSet = openSet;
        this.closeSet = closeSet;
    }


    public int test(String expression){
        // Returns 0 if expression is balanced.
        // Returns 1 if expression has unbalanced symbols.
        // Returns 2 if expression came to end prematurely.
        char currChar;
        int currCharIndex;
        int lastCharIndex;

        int openIndex;
        int closeIndex;

        boolean stillBalanced=true;

        StackInterface<Integer> stack;
        stack = new ArrayBoundedStack<>(expression.length());

        currCharIndex=0;
        lastCharIndex= expression.length()-1;
        while(stillBalanced && (currCharIndex <= lastCharIndex)){
            currChar = expression.charAt(currCharIndex);
            openIndex = openSet.indexOf(currChar);

            if(openIndex != -1) {
                //current character not in openSet
                //push the current char onto the stack
                stack.push(openIndex);
            }else{
                closeIndex = closeSet.indexOf(currChar);
                if(closeIndex != -1){ //current character in closeSet
                    try{
                        //try to pop an index off the stack
                        openIndex = stack.top();
                        stack.pop();
                        if(openIndex != closeIndex){
                            //not match, then not balanced
                            stillBalanced = false;
                        }
                    }catch(StackUnderflowException e){
                        // if stack was empty
                        stillBalanced = false;
                    }
                }
            }
            currCharIndex++;
            //set up processing of next character
        }
        if(!stillBalanced){
            //unbalanced symbols
            return 1;
        }else if(!stack.isEmpty()){
            //premature end of expression
            return 2;
        }else{
            //expression is balanced
            return 0;
        }
    }
}

测试代码：

package Algorithms;

import java.util.Scanner;

public class TestBalanceChecker {
    public static void main(String[] args) {
        BalanceChecker bc = new BalanceChecker("([{", ")]}");
        Scanner sc = new Scanner(System.in);

        //0=balanced, 1=unbalanced, 2 = premature end
        int result;

        String expresison = null;
        final String STOP="X"; //Indicate the end of input

        while(!STOP.equalsIgnoreCase(expresison)){
            //Get next expression to be processed
            System.out.println("Expression ("+STOP+ " to stop): ");
            expresison = sc.nextLine();
            if(!STOP.equalsIgnoreCase(expresison)){
                //Obtain and output result of balanced testing
                result= bc.test(expresison);
                if(result == 1){
                    System.out.println("Unbalanced");
                }else if(result == 2){
                    System.out.println("Premature end of expression ");
                }else{
                    System.out.println("Balanced ");
                }
            }
        }
    }
}