java的栈和用栈来解析算术表达式

废话不多说,直接上代码, 栈是最简单的数据及结构, 可以使用数组实现也可以用链表实现. 并且有对泛型的支持.
接口

public interface Stack<E> {
    boolean isEmpty();
    E peek();
    E pop();
    void push(E item);
    int size();
}

这是个用链表实现的stack.

public class GenericLinkedStack<E> implements Stack<E> {

    private class Node<T>{
        private T data;
        private Node<T> next;



        private Node(T data,Node<T> next){
            this.data=data;
            this.next=next;
        }
    }

    private Node<E> top;
    private int size;

    public void push(E item){
        top=new Node(item, top);
        size++;
    }

    public E pop(){
        E result=top.data;
        top=top.next;
        size--;
        return result;
    }

    public int size(){
        return size;
    }

    public E peek(){
        return top.data;
    }

    public boolean isEmpty(){
        return size==0;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Stack<Integer> s = new GenericLinkedStack<>();
        System.out.println(s.isEmpty());
        for(int i=0;i<5;i++){
            s.push(i);
        }
        for(int i=0;i<10;i++){
            s.push(i);
        }
        System.out.println(s.isEmpty());
        System.out.println(s.peek());
        System.out.println(s.size());
        System.out.println(s.pop());

        Stack<Double> d= new GenericLinkedStack<>();
        System.out.println(d.isEmpty());
        Random gen = new Random();

        for(int i=0;i<10;i++){
            d.push(gen.nextGaussian());
        }
        System.out.println(d.isEmpty());
        System.out.println(d.peek());
        System.out.println(d.size());
        System.out.println(d.pop());
    }
}

下面的是数组的.

public class GenericArrayStack<E> implements Stack<E>{
    private int top=-1;
    private E[] data;
    private static final int DEFAULT_CAPACITY=10;

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

    public int size(){
        return data.length;
    }

    //constructor
    public GenericArrayStack(){
        data=(E[])new Object[DEFAULT_CAPACITY];
    }

    public E peek(){
        return data[top];
    }

    public void push(E elem){
        if(top==data.length-1)
            resize(2*data.length);
        data[++top]=elem;
    }

    public E pop(){
        if(isEmpty()) throw new EmptyStackException();
        return data[top--];
    }

    public void resize(int newCapacity){
        E[] newdata = (E[])new Object[newCapacity];
        for(int i=0;i<=top;i++){
            newdata[i]=data[i];
        }
        data=newdata;
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Stack<Integer> s = new GenericArrayStack<>();
        System.out.println(s.isEmpty());

        for(int i=0;i<10;i++){
            s.push(i);
        }
        System.out.println(s.isEmpty());
        System.out.println(s.peek());
        System.out.println(s.size());
        System.out.println(s.pop());
    }
}

下面是解析算术表达式

package tree;

public class Expression {
    private static int rank(String op){
        switch(op){
        case "*":
        case "/":
            return 2;
        case "+":
        case "-":
            return 1;
        default :
            return -1;
        }
    }

    private static final String SPACE=" ";

    public static String toPostfix(String expr){
        StringBuilder result = new StringBuilder();
        Stack<String> operators = new GenericArrayStack<>();
        for(String token: expr.split("\\s+")){
            if(rank(token) > 0){
                while(!operators.isEmpty() &&
                    rank(operators.peek()) >= rank(token)){
                    result.append(operators.pop()+SPACE);
                    }
                operators.push(token);
            }else{
                result.append(token+SPACE);
            }
        }
        while(!operators.isEmpty()){
            result.append(operators.pop()+SPACE);
        }
        return result.toString();
    }

    public static int compute(int i1, int i2, String op){
        int result=0;
        switch(op){
            case "*":
                result = i1 * i2;
                break;
            case "/":
                result = i1 / i2;
                break;
            case "+":
                result = i1 + i2;
                break;
            case "-":
                result = i1 - i2;
                break;
        }
        return result;
    }

    public static int evalPostfix(String exp){
        //Stack results = new GenericArrayStack<>();
        Stack<String> operands = new GenericArrayStack<>();
        int result =0;
        for(String token: exp.split("\\s+")){
            if(rank(token)> 0){
                int oper2=Integer.parseInt(operands.pop());
                int oper1=Integer.parseInt(operands.pop());
                result = compute(oper1, oper2, token);
                //System.out.println(result);
                operands.push(Integer.toString(result,10));
            }else{
                operands.push(token);
            }
        }
        return Integer.parseInt(operands.pop());
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int answer =0;
        String exp = "3 5 1 - *";
        answer = evalPostfix("3 5 1 - *");
        System.out.println(answer);

        String exp2= "5 - 1 + 3 * 2";
        System.out.println(evalPostfix(toPostfix(exp2)));
    }

}