栈和队列一（）

1、类型

最大栈
最小栈
流式数据的最小值
单调队列
两个栈实现一个队列
栈的前缀后缀表达式求值
栈的出栈序列判断
其他

2、基本应用

1） 150. 逆波兰表达式求值后缀表达式求值

波兰表达式计算 > 输入: ["2", "1", "+", "3", "*"] > 输出: 9

解释: ((2 + 1) * 3) = 9

学栈的时候，我们需要两个栈，一个是符号栈，一个是操作数栈，（）需要去除。

import java.util.Stack;
class Solution {
    //后缀表达式求值
    public int evalRPN(String[] tokens) {
        Stack<Integer> s = new Stack<>();

        for(String s1:tokens){
            if(s1.equals("+")||s1.equals("-")||s1.equals("/")||s1.equals("*")){
                int a = s.pop();
                int b = s.pop();
                if(s1.equals("+")){
                    s.push(b+a);
                }else if(s1.equals("-")){
                    s.push(b-a);
                }else if(s1.equals("*")){
                    s.push(b*a);
                }else{
                    s.push(b/a);
                }
            }
            else
            //这个整数进栈
                s.push(Integer.parseInt(s1));
        }
        //最后一个数
        return s.pop();
    }
}

做完这道题，我们先来回顾以下相关知识点。（图解），这里代码实现了如下内容：

3、实现前序、后序、中序表达式的互相转化及构建二叉树（代码实现）

方法讲解参考：

https://blog.csdn.net/walkerkalr/article/details/22798365

在这里插入图片描述

/**
 * @author 60417
 * @date 2021/10/1
 * @time 9:56
 * @todo
 */
package Stack;

import javax.swing.plaf.synth.SynthOptionPaneUI;
import java.util.Stack;

/**
 * 利用stack实现：
 * 1、前缀表达式转后缀表达式
 *      ----前缀表达式求值
 * 2、中缀表达式转后缀表达式
 *      ----中缀表达式求值
 * 3、后缀表达式求值
 *      ----后缀表达式求值
 * 4、中缀表达式转为一颗二叉树   特点：叶子节点是操作数，其他节点为操作符
 *
 * 概念介绍和复习：
 * 前缀表达式 是一种没有括号的算术 表达式 ，与 中缀表达式 不同的是，其将运算符写在前面，操作数写在后面。
 * 后缀表达式 则是将操作数写在前面，运算符写在后面。
 *
 * 前缀表达式 又称波兰 表达式 ，后缀表达式 又称逆波兰 表达式 。
 *
 * 二叉树的三种遍历方式对应了上述三种表达式
 *
 */
public class HouZhui_QianZui_MidZhui {
    public static void main(String[] args) {
        //  1+((2/3)*4)-5*6-9*10-6 = 1+0.66*4-30-90-6=1+2.64-126=122.33333...
        String[] mid = {"1","+", "(","(","2","/", "3",")","*","4",
                ")", "-" ,"5","*","6","-","9","*","10","-","6"};
//        String[] mid = new String[]{"(","2","+","5",")","*","3","+","1"};
        System.out.println("中缀表达式");
        printStringArray(mid);
        String[] strings = MidZhuiToHouZhui(mid);
        System.out.println("后缀表达式");
        printStringArray(strings);
        double v = CountHouZhui(strings);
        System.out.println(v);
        String[] strings1 = MidZuiToQianZhui(mid);
        System.out.println("前缀表达式");
        printStringArray(strings1);
        double v1 = CountQianZhui(strings1);
        System.out.println(v1);

        System.out.println(CountMidZhui(mid));
        System.out.println("==================后缀转中缀====================");
        //后缀转中缀
        System.out.println("后缀逆序为中缀");
        printStringArray(strings);//后缀
        String[] strings2 = HouZhuiToMid(strings);
        printStringArray(strings2);

        System.out.println("格式化完毕");
        //利用转化的中缀再反过来计算一次看以下对不：
        System.out.println("计算后缀：");
        String[] strings3 = MidZhuiToHouZhui(strings2);//转后缀：这里因为没有添加好=号分割除每一个符号所以有点难难计算
        System.out.println("转化的后缀表达式：");
        printStringArray(strings3);
        System.out.println("计算前缀");
        String[] strings4 = MidZuiToQianZhui(strings2);
        System.out.println("转化的前缀表达式：");
        printStringArray(strings4);

        System.out.println("计算每一种表达式的值");
        System.out.println(CountQianZhui(strings4));
        System.out.println(CountHouZhui(strings3));
        System.out.println(CountMidZhui(strings2));


        System.out.println("======后缀表达式构造二叉树=======");//strings
        TreeNode treeNode = constructTreeByMinZhui(strings);
        treeNode.traver(0);
        treeNode.traver(1);
        treeNode.traver(2);




    }

    /**
     * 工具函数，打印字符数组
     * @param token
     */
    public static void printStringArray(String[] token){
        if(token==null || token.length==0){
            System.out.print("null");
            return;
        }
        for(String s:token){
            System.out.print(s);
        }
        System.out.println();
    }
    /**
     * 返回算法符号的优先级：
     * 基本符号 + - * /
     * 括号: ()
     * @param operator
     * @return
     */
    public static int priority(String operator){
        if(operator==null || operator.length()>=2){
            return -1;//不存在的优先级
        }
        int priority = -1;
        switch (operator){
            case "*":
            case "/":priority = 2;break;
            case "+":
            case "-":priority = 1;break;
            case "(":
            case ")":priority = 0;break;
            default: break;
        }
        return priority;
    }
    /**
     * 后缀表达式 转中缀表达式
     * @param tokens 输入的合法 前缀表达式
     * @return 后缀表达式
     */
    public static String[] HouZhuiToMid(String[] tokens){
        //根据后缀表达式求值的过程就是一个中缀表达式的计算过程，只不过去除了括号，我们可以手动添加：
        //前缀表达式和后缀表达式的区别就是需要逆序遍历，然后操作数
        //遍历每个字符，数字就入栈，运算符则弹出两个操作数，对应右操作数和左操作数，运算结果 入栈：
        System.out.println("后缀转中缀表达式");
        Stack<String> stack = new Stack<>();
        for(String s:tokens){
            if("".equals(s)||s==null){
                continue;
            }
            //判断是符号还是数子：
            if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")||s.equals("(")||s.equals(")")){
                String a1 = stack.pop();//操作数
                String a2 = stack.pop();
                switch (s){
                    case "+":stack.push("(="+a2+"=+="+a1+"=)=");break;  //  插入(a2+a1)
                    case "/":stack.push(a2+"=/="+a1+"=");break;
                    case "*":stack.push(a2+"=*="+a1+"=");break;
                    case "-":stack.push("(="+a2+"=-="+a1+"=)=");break;//=用来分割
                }
            }else {//后缀直接插入
                stack.push(s+"=");
            }
        }
        StringBuilder s = new StringBuilder();
        while(!stack.isEmpty()){
            s.append(stack.pop());
        }
        String[] split = s.toString().split("=");
        StringBuilder s2 = new StringBuilder();
        int i=0;
        for(String temp :split){
            if(!"".equals(temp)){
                s2.append(temp);
                s2.append("=");

            }
        }
        return s2.toString().split("=");

    }


    /**
     * 中缀转前缀   从右往左扫描，使得符号位于操作数前面（通过追加字符串然后翻转）
     * @param tokens
     * @return
     */
    public static String[] MidZuiToQianZhui(String[] tokens){
        //前缀表达式和后缀表达式的区别就是需要逆序遍历，然后操作数
        StringBuilder hou_tokens = new StringBuilder();//表达式，使用=分割每个符号和操作数
        Stack<String> stack = new Stack<>();//存储符号
        for(int i=tokens.length-1;i>=0;i--){
            String s = tokens[i];//从后面扫描
            //判断是符号还是数字：
            if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")||s.equals("(")||s.equals(")")){
                if(stack.isEmpty()){
                    stack.push(s);
                }else{
                    if(s.equals(")")){//这里
                        stack.push(s);
                        continue;
                    }
                    String peek = stack.peek();
                    int peek1 = priority(peek);//栈顶符号优先级
                    int s1 = priority(s);//当前符号优先级

                    if(s1>=peek1){//当前符号大于等于栈顶符号，入栈
                        stack.push(s);
                    }else{
                        //取出当前符号
                        //判断是不是“)”
                        if(s.equals("(")){//需要不断弹栈直到遇到“）”
                            //因为我们这里的表达式是合法的 所以不判空了
                            while(!stack.peek().equals(")")){
                                hou_tokens.append(stack.pop());
                                hou_tokens.append("=");
                            }
                            //此时stack.peek()==")"
                            stack.pop();
                        }else{
                            //s1<=peek1  不是）  则需要把栈顶元素弹出到末尾：
                            while(!stack.isEmpty() &&  priority(stack.peek())>s1){
                                hou_tokens.append(stack.pop());
                                hou_tokens.append("=");
                            }
                            stack.push(s);
                        }
                    }
                }

            }else {
                //数字：直接输出
                hou_tokens.append(s);
                hou_tokens.append("=");//=号分隔
            }
        }
        while (!stack.isEmpty()){
            hou_tokens.append(stack.pop());
            hou_tokens.append("=");
        }
//        System.out.println();
//        System.out.println("转化后的=分割表达式");
//        System.out.println(hou_tokens);
        //这里需要翻转 这里需要注意，如果是个位数的逆序没有问题，但是如果是10 逆序变为了01错误了
//        return hou_tokens.reverse().toString().split("=");
        String[] split = hou_tokens.toString().split("=");
        String[] s = new String[split.length];
        int c=0;
        for(int i=split.length-1;i>=0;i--){
            s[c++] = split[i];
        }
        return s;
    }

    /**
     * 中缀表达式转后缀表达式   扫描方式从左到右，进而符号位于操作数的后面
     * @param tokens 输入的合法 前缀表达式
     * @return 后缀表达式
     */
    public static String[] MidZhuiToHouZhui(String[] tokens){
        //前缀表达式和后缀表达式的区别就是需要逆序遍历，然后操作数
        StringBuilder hou_tokens = new StringBuilder();//表达式，使用=分割每个符号和操作数
        Stack<String> stack = new Stack<>();//存储符号
        for(String s:tokens){
            //判断是符号还是数子：
            if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")||s.equals("(")||s.equals(")")){
                if(stack.isEmpty()){
                    stack.push(s);
                }else{
                    if(s.equals("(")){
                        stack.push(s);
                        continue;
                    }
                    String peek = stack.peek();
                    int peek1 = priority(peek);//栈顶符号优先级
                    int s1 = priority(s);//当前符号优先级

                    if(s1>peek1){//当前符号大于栈顶符号，入栈 同级呢？
                        stack.push(s);
                    }else{
                        //取出当前符号
                        //判断是不是“)”
                        if(s.equals(")")){//需要不断弹栈直到遇到“）”
                            //因为我们这里的表达式是合法的 所以不判空了
                            while(!stack.peek().equals("(")){
                                hou_tokens.append(stack.pop());
                                hou_tokens.append("=");
                            }
                            //此时stack.peek()=="("
                            stack.pop();
                        }else{
                           //一直弹，直到栈顶符号优先级小于s1
                            while(!stack.isEmpty() &&  priority(stack.peek())>=s1){
                                hou_tokens.append(stack.pop());
                                hou_tokens.append("=");
                            }
                            stack.push(s);

                        }
                    }
                }

            }else {
                //数字：直接输出
                hou_tokens.append(s);
                hou_tokens.append("=");//=号分隔
            }
        }
        while (!stack.isEmpty()){
            hou_tokens.append(stack.pop());
            hou_tokens.append("=");
        }
        return hou_tokens.toString().split("=");
    }

    /**
     * 后缀表达式 求值
     * @param tokens 输入的合法 后缀表达式
     * @return 结果
     */
    public static double CountHouZhui(String[] tokens){
        //前缀表达式和后缀表达式的区别就是需要逆序遍历，然后操作数
        //遍历每个字符，数字就入栈，运算符则弹出两个操作数，对应右操作数和左操作数，运算结果 入栈：
        Stack<Double> stack = new Stack<>();
        System.out.println("计算后缀表达式");
        printStringArray(tokens);
        for(String s:tokens){
            if("".equals(s)||s==null){
                continue;
            }
            //判断是符号还是数子：
            if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")||s.equals("(")||s.equals(")")){
                double a1 = stack.pop();
                double a2 = stack.pop();
                switch (s){
                    case "+":stack.push(a2+a1);break;
                    case "/":stack.push(a2/a1);break;
                    case "*":stack.push(a2*a1);break;
                    case "-":stack.push(a2-a1);break;
                }
            }else {
                stack.push((double) Integer.parseInt(s));
            }
        }
        return stack.pop();

    }
    /**
     * 前缀表达式 求值
     * @param tokens 输入的合法 前缀表达式
     * @return 结果
     */
    public static double CountQianZhui(String[] tokens){
        //前缀表达式和后缀表达式的区别就是需要逆序遍历，然后操作数
        Stack<Double> stack = new Stack<>();
        System.out.println("计算前缀表达式");
        printStringArray(tokens);
        for(int i=tokens.length-1;i>=0;i--){//
            String s = tokens[i];
            if("".equals(s)||s==null){
                continue;
            }
            //判断是符号还是数子：
            if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")||s.equals("(")||s.equals(")")){
                double a2 = stack.pop();//这里，a1和a2对应的位置
                double a1 = stack.pop();
                switch (s){
                    case "+":stack.push(a2+a1);break;
                    case "/":stack.push(a2/a1);break;
                    case "*":stack.push(a2*a1);break;
                    case "-":stack.push(a2-a1);break;
                }
            }else {
                stack.push((double) Integer.parseInt(s));
            }
        }
        return stack.pop();
    }
    /**
     * 中缀表达式 求值
     * @param tokens 输入的合法 前缀表达式
     * @return 结果
     */
    public static double CountMidZhui(String[] tokens){
        //中缀表达式就是先转为后缀表达式再计算：
        System.out.println("计算中缀表达式 转化后缀表达式再计算");
        printStringArray(tokens);
        String[] strings = MidZhuiToHouZhui(tokens);
        return  CountHouZhui(strings);
    }

    /**
     * 根据后缀表达式构建中缀表达式树：
     */
    public static TreeNode constructTreeByMinZhui(String[] tokens){
//        在遍历到操作数时建立新节点并将该节点压入操作数栈中。
//        当操作符从操作符栈中出栈时为该操作符新建一个节点，并从操作数栈中pop出两个操作数节点，
//        将第一个操作数节点作为新节点的右节点，第二个个作为左节点，之后将这个新节点压入操作数栈中。
//        当最后一个操作符出栈时，就构成了二叉树，且最后一个操作符节点为根节点。

            if(tokens==null||tokens.length==0){
                return null;
            }
            System.out.println("构建树");
            printStringArray(tokens);
            Stack<TreeNode> stack = new Stack<>();//栈

            for(String s:tokens){
                //判断是符号还是数子：
                if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")||s.equals("(")||s.equals(")")){
                   //操作符：
                    if(s.equals("(") ||s.equals(")")){
                        continue;
                    }
                    TreeNode treeNode = new TreeNode(s);
                    treeNode.right = stack.pop();//第一个弹出的是右孩子
                    treeNode.left = stack.pop();
                    stack.push(treeNode);
                }else {//数字，则构建节点，进栈
                    stack.push(new TreeNode(s));
                }
            }
//            while (stack.isEmpty()){
//                if(stack.size()==1){
//                    return stack.pop();
//                }else {
//                    TreeNode right = stack.pop();
//                    TreeNode left = stack.pop();
//                    return null;
//
//                }
//            }
        return stack.pop();



    }
    static class TreeNode {
        String val;//节点的值：
        TreeNode left;
        TreeNode right;

        public TreeNode(String val) {
            this.val = val;
        }

        public TreeNode(String val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
        public void traver(int i){//遍历二叉树，0前序遍历，1中序遍历，2后序遍历
            if(i==0){
                System.out.println("前序遍历");
                preTraver(this);
                System.out.println();
            }
            else if(i==1){
                System.out.println("中序遍历");
                midTraver(this);
                System.out.println();
            }else if(i==2){
                System.out.println("后续遍历");
                postTraver(this);
                System.out.println();
            }else {
                throw new RuntimeException("不支持的参数！");
            }
        }

        private void postTraver(TreeNode root) {
            if(root==null){
                return;
            }
            postTraver(root.left);
            postTraver(root.right);
            System.out.print(root.val+" ");
        }

        private void midTraver(TreeNode root) {
            if(root==null){
                return;
            }
            midTraver(root.left);
            System.out.print(root.val+" ");
            midTraver(root.right);
        }

        private void preTraver(TreeNode root) {
            if(root==null){
                return;
            }
            System.out.print(root.val+" ");
            preTraver(root.left);
            preTraver(root.right);
        }
    }
}