java 實現 stack

棧是限制插入和刪除只能在一個位置上進行的 List，該位置是 List 的末端，叫做棧的頂(top)，對于棧的基本操作有 push 和 pop，前者是插入，后者是刪除。

棧也是 FIFO 表。

棧的實現有兩種，一種是使用數組，一種是使用鏈表。

public class MyArrayStack<E> {

    private ArrayList<E> list = new ArrayList<>();

    public void push(E e) {
        list.add(e);
    }

    public E pop() {
        return list.remove(list.size() - 1);
    }

    public E peek() {
        return list.get(list.size() - 1);
    }

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

public class MyLinkStack<E> {

    LinkedList<E> list = new LinkedList<>();

    public void push(E e) {
        list.addLast(e);
    }

    public E pop() {
        return list.removeLast();
    }

    public E peek() {
        return list.getLast();
    }

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

棧的應用

平衡符號

給定一串代碼，我們檢查這段代碼當中的括號是否符合語法。

例如：[{()}] 這樣是合法的，但是 [{]}() 就是不合法的。

如下是測試代碼：

public class BalanceSymbol {

    public boolean isBalance(String string) {
        MyArrayStack<Character> stack = new MyArrayStack<>();
        char[] array = string.toCharArray();
        for (char ch : array) {
            if ("{[(".indexOf(ch) >= 0) {
                stack.push(ch);
            } else if ("}])".indexOf(ch) >= 0) {
                if (isMatching(stack.peek(), ch)) {
                    stack.pop();
                }
            }
        }

        return stack.isEmpty();
    }

    private boolean isMatching(char peek, char ch) {
        if ((peek == '{' && ch == '}') || (peek == '[' && ch == ']') || (peek == '(' && ch == ')')) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        BalanceSymbol symbol = new BalanceSymbol();
        String string = "public static void main(String[] args) {BalanceSymbol symbol = new BalanceSymbol();}";
        String string2 = "public static void main(String[] args) {BalanceSymbol symbol = new BalanceSymbol([);}]";
        System.out.println(symbol.isBalance(string));
        System.out.println(symbol.isBalance(string2));
    }
}

后綴表達式

例如一個如下輸入，算出相應的結果，

3 + 2 + 3 * 2 = ?

這個在計算順序上不同會產生不同的結果，如果從左到右計算結果是 16，如果按照數學優先級計算結果是 11。

如果把上述的中綴表達式轉換成后綴表達式：

3 2 + 3 2 * +

如果使用后綴表達式來計算這個表達式的值就會非常簡單，只需要使用一個棧。

每當遇到數字的時候，把數字入棧。

每當遇到操作符，彈出2個元素根據操作符計算后，入棧。

最終彈出棧的唯一元素就是計算結果。

/**
 * 簡化版本，每個操作數只一位，并且假設字符串合法
 */
public class PostfixExpression {

    public static int calculate(String string) {
        MyArrayStack<String> stack = new MyArrayStack<>();

        char[] arr = string.toCharArray();

        for (char ch : arr) {
            if ("0123456789".indexOf(ch) >= 0) {
                stack.push(ch + "");
            } else if ("+-*/".indexOf(ch) >= 0) {
                int a = Integer.parseInt(stack.pop());
                int b = Integer.parseInt(stack.pop());
                if (ch == '+') {
                    stack.push((a + b) + "");
                } else if (ch == '-') {
                    stack.push((a - b) + "");
                } else if (ch == '*') {
                    stack.push((a * b) + "");
                } else if (ch == '/') {
                    stack.push((a / b) + "");
                }
            }
        }
        return Integer.parseInt(stack.peek());
    }

    public static void main(String[] args) {
        System.out.println(calculate("32+32*+"));
    }
}

中綴表達式轉換成后綴表達式

假設只運行 +，-，*，/，() 這幾種表達式。并且表達式合法。

a + b * c - (d * e + f) / g 轉換后的后綴表達式如下：

a b c * + d e * f + g / -

使用棧中綴轉后綴步驟如下：

• 當讀到操作數立即把它輸出

• 如果遇到操作符入棧，如果遇到的左括號也放到棧中

• 如果遇到右括號，就開始彈出棧元素，直到遇到對應的左括號，左括號只彈出不輸出。

• 如果遇到其他符號，那么從棧中彈出棧元素知道發現優先級更低的元素為止。

import java.util.HashMap;
import java.util.Map;

public class ExpressionSwitch {

    private static Map<Character, Integer> map = new HashMap<Character, Integer>();

    static {
        map.put('+', 0);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 3);
        map.put('(', 4);
    }

    private static char[][] priority = {
            // 當前操作符
            //           +    -    *    /    ( 
            /* 棧 + */{ '>', '>', '<', '<', '<'},
            /* 頂 - */{ '>', '>', '<', '<', '<'},
            /* 操 * */{ '>', '>', '>', '>', '<'},
            /* 作 / */{ '>', '>', '>', '>', '<'},
            /* 符 ( */{ '<', '<', '<', '<', '<'},
    };

    public static String switch1(String string) {
        StringBuilder builder = new StringBuilder();

        char[] arr = string.toCharArray();

        MyArrayStack<Character> stack = new MyArrayStack<>();
        for (char ch : arr) {
            if ("0123456789abcdefghijklmnopqrstuvwxyz".indexOf(ch) >= 0) {
                builder.append(ch);
            } else if ('(' == ch) {
                stack.push(ch);
            } else if (')' == ch) {
                while (true && !stack.isEmpty()) {
                    char tmp = stack.pop();
                    if (tmp == '(') {
                        break;
                    } else {
                        builder.append(tmp);
                    }
                }
            } else {
                while (true) {
                    if (stack.isEmpty()) {
                        stack.push(ch);
                        break;
                    }
                    char tmp = stack.peek();
                    if (isPriorityHigh(tmp, ch)) {
                        builder.append(stack.pop());
                    } else {
                        stack.push(ch);
                        break;
                    }
                }
            }
        }

        while(!stack.isEmpty()) {
            builder.append(stack.pop());
        }

        return builder.toString();
    }

    private static boolean isPriorityHigh(char tmp, char ch) {
        return priority[map.get(tmp)][map.get(ch)] == '>';
    }

    public static void main(String[] args) {
        System.out.println(switch1("a+b*c-(d*e+f)/g"));
    }
}

來自：http://renchx.com/java-stack