栈

栈模型(LIFO)

限制插入和删除只能在一个位置进行的表，即栈顶操作。

基本操作

• push()
• pop()
• top()

栈的实现

ArrayList和LinkedList都支持栈操作。可以使用链式结构或者使用数组。

栈的应用

• 平衡符号

package top.carrotguo.stack.apply;

import com.sun.org.apache.xerces.internal.impl.xpath.regex.Match;
import top.carrotguo.bean.stack.Stack;

/**
 * 括号匹配
 * @Author: Carrot
 * @Mail: 1053155183carrot@gmail.com
 * @Date: Created in 13:14 2018-06-10
 */
public class Matching {

    //表达式
    private String expression;
    private String e;
    //简化后只有括号的表达式
    private String simple="";
    private Stack<Character> stack;

    public Matching(String expression){
        this.expression = expression;
        stack = new Stack<>();
    }

    /**
     * 简化表达式只保存括号
     */
    private void simply(){
        for (int i=0; i<expression.length(); i++) {
            if (expression.charAt(i)=='('
                    || expression.charAt(i)==')'
                    || expression.charAt(i)=='['
                    || expression.charAt(i)==']'
                    || expression.charAt(i)=='{'
                    || expression.charAt(i)=='}') {
                simple += expression.charAt(i);
            }
        }
        System.out.println(simple);
    }

    /**
     * 括号匹配
     */
    public boolean isMatch(){
        //简化表达式（留括号）
        simply();
        for (int i=0; i<simple.length(); i++) {
            char e = simple.charAt(i);
            if (e == '(' || e == '[' || e == '{') {
                //左括号进栈
                stack.push(e);
            } else if (!stack.isEmpty()) {
                //右括号且栈非空  出栈一个左括号
                if (e==')'&&stack.top()=='(') {
                    stack.pop();
                } else if (e==']' && stack.top()=='[') {
                    stack.pop();
                } else if (e=='}' && stack.top()=='{') {
                    stack.pop();
                }
            } else {
                //右括号还存在 但栈已空 无法匹配
                return false;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args){
        Matching matching = new Matching("{[(3+1)*(3+6)]+(3-5)}+(3+5)");
        boolean isMatch = matching.isMatch();
        if (isMatch) {
            System.out.println("匹配成功");
        } else {
            System.out.println("匹配失败");
        }
    }


}

• 进制转换

package top.carrotguo.stack.apply;

import top.carrotguo.bean.stack.Stack;

/**
 * 进制转换
 * @Author: Carrot
 * @Mail: 1053155183carrot@gmail.com
 * @Date: Created in 22:09 2018-06-09
 */
public class Conversion {
    //进制对应数字的表示形式（如十六进制的10写为A）
    private String[] digit = {"0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"};
    //存储余数的栈
    private Stack<String> remainder = new Stack();

    /**
     * 进制转换
     * @param n
     * @param base  base进制
     */
    public void convert(int n,int base){
        String result = null;
        while (n>0) {
            //余数进栈
            remainder.push(digit[n%base]);
            n /= base;
        }
        System.out.print(n+"进行"+base+"进制转换 >>> ");
        while ((result=remainder.pop()) != null) {
            System.out.print(result+" ");
        }
    }

    public static void main(String[] args){
        Conversion conversion = new Conversion();
        conversion.convert(257,16);
    }

}

• 后缀表达式（逆波兰式）求值

package top.carrotguo.leetcode.stack;

import java.util.Stack;

/**
 * 后缀表达式求值
 * @Author: Carrot
 * @Mail: 1053155183carrot@gmail.com
 * @Date: Created in 20:52 2018-07-18
 */
public class Solution {
    private Stack<Integer> numStack = new Stack();
    private Stack<Character> optrStack = new Stack();

    public int evalRPN(String[] tokens) {
        for(String str : tokens){
            if(!str.equals("+")&&!str.equals("-")&&!str.equals("*")&&!str.equals("/")){
                numStack.push(Integer.valueOf(str));
            } else {
                switchCalu(str);
            }
        }
        return numStack.pop();
    }

    private void switchCalu(String op){
        int num2 = numStack.pop();
        int num1 = numStack.pop();
        int result = 0;
        switch(op){
            case "+":{
                result = num1+num2;
                break;
            }
            case "-":{
                result = num1-num2;
                break;
            }
            case "*":{
                result = num1*num2;
                break;
            }
            case "/":{
                result = num1/num2;
                break;
            }
        }
        numStack.push(result);
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        int result1 = solution.evalRPN(new String[]{"2","1","+","3","*"});
        int result2 = solution.evalRPN(new String[]{"4","13","5","/","+"});
        System.out.println(result1);
        System.out.println(result2);
    }
}

• 中缀表达式转后缀表达式

package top.carrotguo.stack.apply;

import top.carrotguo.bean.stack.Stack;

import java.util.regex.Pattern;

/**
 * 中缀表达式转后缀表达式
 * @Author: Carrot
 * @Mail: 1053155183carrot@gmail.com
 * @Date: Created in 21:08 2018-06-13
 */
public class InfixToPostfix {

    private String iExpression;      //中缀表达式
    private Stack<Float> opnd;   //数字栈
    private Stack<Character> optr;   //符号栈
    private String pExpression = "";      //后缀表达式
    //优先级表
    private char[][] pri = {/*----------------当前运算符----------------------*/
                            /*+   -   *   /   ^   !   (   )   \0*/
                            /*-- + */ {'>','>','<','<','<','<','<','>','>'}
                            /*|  - */,{'>','>','<','<','<','<','<','>','>'}
                            /*栈 * */,{'>','>','>','>','<','<','<','>','>'}
                            /*顶 / */,{'>','>','>','>','<','<','<','>','>'}
                            /*运 ^ */,{'>','>','>','>','>','<','<','>','>'}
                            /*算 ! */,{'>','>','>','>','>','>',' ','>','>'}
                            /*符 ( */,{'<','<','<','<','<','<','<','=',' '}
                            /*|  ) */,{' ',' ',' ',' ',' ',' ',' ',' ',' '}
                            /*--\0 */,{'<','<','<','<','<','<','<',' ','='}};

    /**
     * @param express   中缀表达式
     */
    public InfixToPostfix(String express){
        iExpression = express+'\0';
        //初始化栈
        opnd = new Stack<>();
        optr = new Stack<>();
    }

    /**
     * 中缀表达式转后缀表达式
     * @return 后缀表达式
     */
    public String conver(){
        optr.push('\0');        //表达式起始符号进栈,用于控制所有符号出栈并且判断是否扫描完整个表达式
        int index = 0;            //当前扫描表达式的字符的索引
        char e;                   //当前扫描表达式的字符

        //中缀表达式转后缀表达式
        while (!optr.isEmpty()) {
            e = iExpression.charAt(index);
            //数字则读取数字并且追加到后缀表达式
            if (isNum(e)) {
                //读取数字  扫描的位置定位到下一个符号位置
                index = readNum(index)+1;
                pExpression += opnd.top()+" ";
            } else {
                //操作符处理
                //1 根据优先级处理
                //2 将index定位 进行下一轮循环
                index = switchOperate(optr.top(),index);
            }
        }
        return pExpression;
    }

    /**
     * 根据优先级处理符号
     * @param top   栈顶符号
     * @param index 当前扫描的符号
     * @return      下一次循环应该扫描的位置
     */
    private int switchOperate(char top, int index){
        char e = iExpression.charAt(index);
        char priority = orderBetween(top,e);        //获取优先级比较
        //根据优先级不同进行处理
        switch (priority) {
            case '<' : {
                //栈顶元素优先级低于当前扫描符-->直接进栈,下一次扫描位置后移一位
                optr.push(e);
                index++;
                break;
            }
            case '=' : {
                //')'或者'\0'情况-->只需栈顶弹栈,下一次扫描位置后移一位
                optr.pop();
                index++;
                break;
            }
            case '>' : {
                //栈顶元素弹栈，追加到后缀表达式中,下一次扫描位置不变
                pExpression += optr.pop()+" ";
                break;
            }
        }
        return index;
    }

    /**
     * 返回优先级比较
     * @param top   栈顶符号
     * @param e     当前扫描符号
     * @return      > < =
     */
    private char orderBetween(char top, char e){
        String digit = "+-*/^!()\0";
        int topIndex = digit.indexOf(top);
        int eIndex = digit.indexOf(e);
        return pri[topIndex][eIndex];
    }

    /**
     * 判断是否是数字
     * @param c
     * @return
     */
    private boolean isNum(char c){
        String num = "0123456789";
        if (num.indexOf(c) != -1) {
            return true;
        }
        return false;
    }

    private boolean isNum(String str){
        Pattern pattern = Pattern.compile("[0-9]+([.]{1}[0-9]+){0,1}");
        return pattern.matcher(str).matches();
    }

    /**
     * 数字转换
     * @param index
     * @return  返回连续的最后一位数字
     */
    private int readNum(int index){
        float num = Float.parseFloat(String.valueOf(iExpression.charAt(index)));

        //判断下一位是否为数字
        if (isNum(iExpression.charAt(index+1))) {
            //index后移一位
            index++;
            num = num*10+Float.parseFloat(String.valueOf(iExpression.charAt(index+1)));
        }
        //数字进栈
        opnd.push(num);
        return index;
    }

    /**
     * 根据后缀表达式计算
     * @return  表达式结果
     */
    public float calculate(String[] postFix){
        float sum = 0;
        //先清空数字栈
        while (!opnd.isEmpty()) {
            opnd.pop();
        }
        for (String str : postFix) {
            if (isNum(str)) {
                //数字进栈
                opnd.push(Float.valueOf(String.valueOf(str)));
            } else {
                //直接计算
                if (str == "!") {
                    //单操作数运算
                    float num = opnd.pop();
                    num = switchPower(num);
                    //计算结果重新入栈
                    opnd.push(num);
                } else {
                    //双操作数运算
                    float num2 = opnd.pop();
                    float num1 = opnd.pop();
                    char op = str.charAt(0);        //此时str必定是操作符  取第一个元素转化为char即为操作符
                    float result = switchCalcu(num1,num2,op);
                    //计算结果入栈
                    opnd.push(result);
                }
            }
        }
        sum = opnd.top();
        return sum;
    }

    /**
     * 根据运算符计算(二元)
     * @return
     */
    public float switchCalcu(float num1,float num2, char operator){
        float result = 0;
        switch (operator) {
            case '+' : {
                result = num1+num2;
                break;
            }
            case '-' : {
                result = num1 - num2;
                break;
            }
            case '*' : {
                result = num1 * num2;
                break;
            }
            case '/' : {
                result = num1 / num2;
                break;
            }
            case '^' : {
                result = (float) Math.pow(num1,num2);
                break;
            }
        }
        return result;
    }

    /**
     * 根据运算符计算（一元）
     * @return
     */
    public float switchPower(float num){
        float sum = 1;
        for (int i=1; i<=num; i++) {
            sum *= i;
        }
        return sum;
    }

    public static void main(String[] args){
        InfixToPostfix infixToPostfix = new InfixToPostfix("(1+2)+5^2+(6-1)");
        //System.out.println(infixToPostfix.conver());
        String[] str = infixToPostfix.conver().split(" ");
        for (String s: str) {
            System.out.print(s+" ");
        }
        float result = infixToPostfix.calculate(str);
        System.out.print("="+result);
    }

}

• 中缀表达式求值

package top.carrotguo.stack.apply;

import top.carrotguo.bean.stack.Stack;

/**
 * 栈应用——中缀表达式求值
 * @Author: Carrot
 * @Mail: 1053155183carrot@gmail.com
 * @Date: Created in 17:14 2018-06-10
 */
public class InfixExpression {
    private char[][] pri = {            /*当前运算符*/
                            /*+   -   *   /   ^   !   (   )   \0*/
                  /*-- + */ {'>','>','<','<','<','<','<','>','>'}
                  /*|  - */,{'>','>','<','<','<','<','<','>','>'}
                  /*栈 * */,{'>','>','>','>','<','<','<','>','>'}
                  /*顶 / */,{'>','>','>','>','<','<','<','>','>'}
                  /*运 ^ */,{'>','>','>','>','>','<','<','>','>'}
                  /*算 ! */,{'>','>','>','>','>','>',' ','>','>'}
                  /*符 ( */,{'<','<','<','<','<','<','<','=',' '}
                  /*|  ) */,{' ',' ',' ',' ',' ',' ',' ',' ',' '}
                  /*--\0 */,{'<','<','<','<','<','<','<',' ','='}};
    private Stack<Character> optr;      //运算符栈
    private Stack<Float> opnd;          //运算数栈
    private String expression;          //表达式

    public InfixExpression(String expression){
        optr = new Stack<>();
        opnd = new Stack<>();
        //末尾加上'\0',  '\0' 用于控制所有操作符出栈
        this.expression = expression+'\0';
    }

    /**
     * 中缀表达式结算——栈的应用
     * @return
     */
    public float evaluate(){
        //先将表达式开始标识符'\0'进栈
        optr.push('\0');
        int i=0;        //记录当前扫描到的字符
        //扫描表达式
        while (!optr.isEmpty()) {
            //是否为数字
            if (isDigit(expression.charAt(i))) {
                //数字进栈（多位数需要进行处理为一个数字再入栈）
                i = readNum(i);
                i++;        //扫描下一位
            } else {   //当前扫描到的为运算符
                //根据优先级处理(scan为扫描过且已进栈的符号个数)
                char top = optr.top();
                int scan = switchOperate(top,expression.charAt(i));
                i += scan;
            }
        }
        return opnd.top();
    }

    /**
     * 根据优先级计算
     * @param top  操作符栈顶元素
     * @param e    当前扫描到的操作符
     */
    private int switchOperate(char top,char e){
        int scan = 0;   //进栈操作符个数
        char priority = orderBetween(top,e);
        switch (priority) {
            case '<' : {
                //栈顶优先级<当前扫描符号--操作符进栈
                optr.push(e);
                scan = 1;
                break;
            }
            case '=' : {
                //栈顶优先级=当前扫描符号--操作符弹栈，扫描表达式下一位(有括号或者\0)
                optr.pop();
                scan = 1;
                break;
            }
            case '>' : {
                char op = optr.pop();   //弹出栈顶操作符
                //单目操作符
                if (op == '!') {
                    opnd.push(calcu(op,opnd.pop()));
                } else {
                    //双目操作符
                    float num2 = opnd.pop();
                    float num1 = opnd.pop();
                    opnd.push(calcu(num1,num2,op));
                }
                scan = 0;
                break;
            }
        }
        return scan;
    }

    /**
     * 单目运算
     * @param op
     * @param num
     * @return  运算结果
     */
    private float calcu(char op, float num){
        float sum = 1;
        if (op == '!') {
            for (int i=1; i<=num; i++) {
                sum *= i;
            }
        }
        return sum;
    }

    /**
     * 双目运算
     * @param num1  第一个操作数
     * @param num2  第二个操作数
     * @param op    操作符
     * @return      结果
     */
    private float calcu(float num1, float num2, char op){
        float result = 0;
        switch (op) {
            case '+' : {
                result = num1 + num2;
                break;
            }
            case '-' : {
                result = num1 - num2;
                break;
            }
            case '*' : {
                result = num1 * num2;
                break;
            }
            case '/' : {
                result = num1 / num2;
                break;
            }
            case '^' : {
                result = (float) Math.pow(num1,num2);
            }
        }
        return result;
    }

    /**
     * 优先级比较（栈顶？当前扫描运算符）
     * @return >  <  =
     */
    private char orderBetween(char top, char e){
        String digit = "+-*/^!()\0";
        int topIndex = digit.indexOf(top);
        int scanDidex = digit.indexOf(e);
        return pri[topIndex][scanDidex];
    }

    /**
     * 判断字符是否为数字
     * @param e
     * @return
     */
    private boolean isDigit(char e){
        String num = "0123456789";
        if (num.indexOf(e)!=-1) {
            return true;
        }
        return false;
    }

    /**
     * 数字转化并进栈（因为多位数是多个字符组成  需要转化为float）
     * @param i   当前扫描到表达式的位置
     * @return    扫描到的最后一个连续数字的位置
     */
    private int readNum(int i){
        float num = Float.parseFloat(String.valueOf(expression.charAt(i)));
        //判断表达式下一位是否是数字，是数字则要进行转换
        while (isDigit(expression.charAt(i+1))) {
            i++;
            num = num*10+Float.parseFloat(String.valueOf(expression.charAt(i)));
        }
        //数字进栈
        opnd.push(num);
        return i;
    }

    public static void main(String[] args){
        InfixExpression infixExpression = new InfixExpression("(1+2)+5^2+(6-1)");
        float result = infixExpression.evaluate();
        System.out.println("计算结果 >> "+result);
    }
}