棧在表達(dá)式求職中的應(yīng)用

分兩個(gè)棧：操作數(shù)棧和數(shù)字棧；
壓棧出棧規(guī)則：遍歷表達(dá)式

• 如果是數(shù)字則直接壓入數(shù)字棧
• 如果是操作符（加減乘除）則將該操作符與操作數(shù)棧的棧頂元素比較：優(yōu)先級(jí)高于棧頂元素則直接壓棧；優(yōu)先級(jí)小于等于棧頂元素則將棧頂元素出棧，并從數(shù)字棧中取兩個(gè)數(shù)字做操作，然后將結(jié)果壓回?cái)?shù)字棧（循環(huán)此過程直至操作數(shù)棧為空或者當(dāng)前操作數(shù)比棧頂元素優(yōu)先級(jí)高）。
• 遍歷完之后，要看操作數(shù)棧是否為空，為空則結(jié)束，并從數(shù)字棧中取出結(jié)果；不為空，則操作數(shù)棧出棧且從數(shù)字棧中取兩個(gè)數(shù)字操作并將結(jié)果壓入棧，循環(huán)如此操作。

進(jìn)階：上面只考慮有操作數(shù)和數(shù)字的情況，沒有考慮括號(hào)的情況
如果考慮括號(hào)，其實(shí)處理思路是差不多的：

• 把右擴(kuò)號(hào)）當(dāng)成優(yōu)先級(jí)最高的，當(dāng)）從操作數(shù)棧出棧時(shí)，還要再連續(xù)出棧兩個(gè)操作數(shù)：一個(gè)運(yùn)算符一個(gè)左括號(hào)，錯(cuò)了；是要一個(gè)一個(gè)操作數(shù)出棧，直至遇到左括號(hào)
• 左括號(hào)（的優(yōu)先級(jí)，定義為和）一樣，不行，其他操作符遇到（就會(huì)讓（出棧，定義為最低級(jí)別也不行，（要入棧的時(shí)候會(huì)讓棧中的操作符全部出棧。所以左括號(hào)要特殊處理，（的優(yōu)先級(jí)定義為最低，但是入棧的時(shí)候直接入

java實(shí)現(xiàn)如下：

import java.util.Stack;
/**
 * 描述：
 * 給定一個(gè)運(yùn)算式，計(jì)算其結(jié)果
 * 這里只是為了演示棧的使用，所以可以將輸入簡化為一個(gè)字符串?dāng)?shù)組，假定字符串要么是數(shù)字，要么是操作運(yùn)算符（加減乘除）,要么是小括號(hào)。不用自己去解析了
 *
 * @author zzz
 * @date 2018/11/14
 */
public class CalculateOperator {

    public static void main(String[] args) {
//        String[] input = new String[]{"(", "(", "1", "-", "2", ")", "*", "(", "3", "-", "5", ")", "+", "4", ")", "/", "2"};

        String[] input = new String[]{"(","5","+","(","1","+","2",")","*","(","3","-","5",")",")","*","2"};

        System.out.println(input.length);

        CalculateOperator co = new CalculateOperator();
        System.out.println(co.calculateOperator(input));
    }

    public int calculateOperator(String[] input) {
        if (input == null || input.length == 0) {
            return 0;
        }

        Stack<String> operateStack = new Stack<>();
        Stack<Integer> digitStack = new Stack<>();

        for (String s : input) {
            if (isDigit(s)) {
                //數(shù)字直接入數(shù)字棧
                digitStack.push(Integer.parseInt(s));
            } else if ("(".equals(s)) {
                operateStack.push(s);
            } else {
                while (true) {
                    if (!operateStack.empty()) {
                        int levelMinus = operateLevel(s) - operateLevel(operateStack.peek());
                        if (levelMinus > 0) {
                            //當(dāng)前操作符優(yōu)先級(jí)高于棧頂操作符則直接入棧
                            operateStack.push(s);
                            break;
                        } else {
                            //否則，將棧頂操作符出棧并取兩個(gè)數(shù)字運(yùn)算，結(jié)果入數(shù)字棧；循環(huán)此過程
                            popCalculatePush(operateStack, digitStack);
                        }
                    } else {
                        operateStack.push(s);
                        break;
                    }
                }
            }
        }

        //處理?xiàng)Ｖ袣堄嗟牟僮鞣?        while (!operateStack.empty()) {
            popCalculatePush(operateStack, digitStack);
        }

        return digitStack.pop();
    }

    private void popCalculatePush(Stack<String> operateStack, Stack<Integer> digitStack) {
        String operator = operateStack.pop();
        if (")".equals(operator)) {
            //需要再出棧一個(gè)操作符和(左括號(hào) bug
            //注意：不一定一個(gè)操作符連著一個(gè)左括號(hào)，右括號(hào)與左括號(hào)中間可能隔著多個(gè)運(yùn)算符，自己運(yùn)算下上面的第二個(gè)input就知道了
            //需要一直出棧知道遇到左括號(hào)(
            operator = operateStack.pop();
            while(!"(".equals(operator) && !operateStack.empty()){
                int y = digitStack.pop();
                int x = digitStack.pop();
                int calRes = calculate(x, y, operator);
                digitStack.push(calRes);

                operator = operateStack.pop();
            }

        } else {
            int y = digitStack.pop();
            int x = digitStack.pop();
            int calRes = calculate(x, y, operator);
            digitStack.push(calRes);
        }
    }

    private int calculate(int x, int y, String operator) {
        switch (operator) {
            case "+":
                return x + y;
            case "-":
                return x - y;
            case "*":
                return x * y;
            case "/":
                return x / y;
            default:
                return 0;
        }
    }

    private boolean isDigit(String str) {
        try {
            int digit = Integer.parseInt(str);
            return true;
        } catch (Exception e) {
            return false;
        }
    }

    private int operateLevel(String s) {
        switch (s) {
            case "+":
            case "-":
                return 1;
            case "*":
            case "/":
                return 2;
            case ")":
                return 3;
            default:
                return 0;
        }
    }
}

棧在括號(hào)匹配中的應(yīng)用

各種括號(hào)組成的字符串：[],(),{}, 判斷字符串的括號(hào)使用是否是合法格式
舉例：{[()]}是合法的，{[}()]不合法
可以用一個(gè)棧就可以判斷：左括號(hào)直接入棧，遇到右括號(hào)直接從出棧一個(gè)符號(hào)，如果與右括號(hào)類型匹配則繼續(xù)，否則為非法格式；最后遍歷完棧為空則合法，棧非空則非法

java實(shí)現(xiàn)如下：

/**
 * 描述：
 * 各種括號(hào)組成的字符串：[],(),{}, 判斷字符串的括號(hào)使用是否是合法格式?
 * 舉例：{[()]}是合法的，{[}()]不合法
 *
 * @author zzz
 * @date 2018/11/14
 */
public class BracketMatch {

    private static final List<Character> leftBracket = Arrays.asList('(','{','[');

    private static final Map<Character,Character> pairs = new HashMap<>();

    static {
        pairs.put('(',')');
        pairs.put('[',']');
        pairs.put('{','}');
    }

    public static void main(String[] args) {
//        String s = "{[()]}[]";
        String s = "{[}()]";
        BracketMatch bracketMatch = new BracketMatch();
        System.out.println(bracketMatch.isBracketMatch(s));
    }

    public boolean isBracketMatch(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(leftBracket.contains(c)){
                stack.push(c);
            } else {
                if(stack.empty()){
                    return false;
                } else {
                    char cPop = stack.pop();
                    boolean isMatch = isLeftRightMatch(cPop, c);
                    if(!isMatch){
                        return false;
                    }
                }
            }
        }

        return stack.empty();
    }

    private boolean isLeftRightMatch(char left, char right){
        if(pairs.get(left) == right){
            return true;
        }
        return false;
    }
}

棧在瀏覽器前進(jìn)、后退、跳轉(zhuǎn)新頁面中的操作

兩個(gè)棧：一個(gè)前進(jìn)棧X，一個(gè)后退棧Y

• 前進(jìn)時(shí)：從后退棧Y中出棧一個(gè)步驟并入棧到前進(jìn)棧X中
• 后退時(shí)：從前進(jìn)棧X中出棧一個(gè)步驟并入棧到后退棧Y中
• 跳轉(zhuǎn)新頁面：清空后退棧Y，并將新步驟入前進(jìn)棧X

java代碼如下：

/**
 * 描述：
 *  棧實(shí)現(xiàn)瀏覽器前進(jìn)、后退、跳轉(zhuǎn)新頁面中的操作
 * @author zzz
 * @date 2018/11/14
 */
public class BrowserForwardOrBack {

    private Stack<Integer> stackX = new Stack<>();

    private Stack<Integer> stackY = new Stack<>();

    public static void main(String[] args) throws Exception{
        BrowserForwardOrBack bfob = new BrowserForwardOrBack();
        bfob.newPage(1);
        bfob.newPage(2);
        bfob.newPage(3);
        bfob.currentPage();//3

        bfob.back();
        bfob.back();
        bfob.forward();
        bfob.currentPage(); //2

        bfob.newPage(4);
        bfob.back();
        bfob.back();
        bfob.forward();
        bfob.currentPage();//2
    }

    public void currentPage(){
        if(!stackX.empty()){
            System.out.println(stackX.peek());
            return;
        }
        System.out.println("current page is not exist");
    }

    /**
     * Y-->X
     * @return
     * @throws Exception
     */
    public boolean forward() throws  Exception{

        if(stackY.empty()){
            throw new Exception("cannot forward");
        }

        stackX.push(stackY.pop());
        return true;
    }

    /**
     * X-->Y
     * @return
     */
    public boolean back() throws Exception{
        if(stackX.empty()){
            throw new Exception("cannot back");
        }

        stackY.push(stackX.pop());
        return true;
    }

    /**
     *
     * @param pageIndex 新頁面的標(biāo)識(shí)，這里直接用數(shù)字表示
     * @return
     */
    public void newPage(int pageIndex){

        //清空stackY
        stackY.clear();

        //入棧stackX
        stackX.push(pageIndex);
    }
}