6, java数据结构和算法: 栈的应用, 逆波兰计算器, 中缀表达式--> 后缀表达式

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了6, java数据结构和算法: 栈的应用, 逆波兰计算器, 中缀表达式--> 后缀表达式，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3649字，纯文字阅读大概需要6分钟。

内容图文

直接上代码:

public class PolandCalculator {
    //栈的应用:波兰计算器:  即: 输入一个字符串,来计算结果, 比如 1+((2+3)×4)-5 结果为16
    public static void main(String[] args) throws Exception {
        /**
         *  思路:
         *  1: 将 1+((2+3)×4)-5 (这叫中缀表达式,运算符再数字中间), 转换为后缀表达式 (1 2 3 + 4 × + 5 –)
         *  2: 使用栈, 将后缀表达式 , 计算得出结果
         *
         *  因为 后缀表达式, 来计算会变得简单易懂, 不需要那么多的判断, 只需要 数入栈,然后判断运算符, 从栈中pop出二个数,计算,并把结果入栈, 循环往复,得到最终结果
         */

        String str = "1+((2+3)*4)-5";
        // 1, 先将 str 字符串变为对应的 中缀表达式 midExpressionList(便于显示)
        List<String> midExpressionList = toMidExpressionList(str);
        System.out.println("前缀表达式为: "+midExpressionList);
        // 2, 将 midExpressionList 转换为 后缀表达式对应的 suffixExpressionList
        List<String> suffixExpressionList = toSuffixExpressionList(midExpressionList);
        System.out.println("后缀表达式为: "+suffixExpressionList);
        // 3, 计算结果
        calculator(suffixExpressionList);
    }

    private static List<String> toMidExpressionList(String s) {
        //定义一个List,存放中缀表达式 对应的内容
        List<String> ls = new ArrayList<String>();
        int i = 0; //这时是一个指针，用于遍历 中缀表达式字符串
        String str; // 对多位数的拼接
        char c; // 每遍历到一个字符，就放入到c
        do {
            //如果c是一个非数字，我需要加入到ls
            if((c=s.charAt(i)) < 48 ||  (c=s.charAt(i)) > 57) {
                ls.add("" + c);
                i++; //i需要后移
            } else { //如果是一个数，需要考虑多位数
                str = ""; //先将str 置成"" '0'[48]->'9'[57]
                while(i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57) {
                    str += c;//拼接
                    i++;
                }
                ls.add(str);
            }
        }while(i < s.length());
        return ls;//返回
    }

    private static List<String> toSuffixExpressionList(List<String> midExpressionList) {
        //1, 定义一个栈 用来存运算符
        Stack<String> cal = new Stack<String>();
        //2, 定义一个list 来做存中间结果和返回,  也可以定义一个栈, 但是用栈的话, 这个转换过程并没有pop操作, 而且还要逆序显示,比较麻烦, 所以用list
        List<String> resList = new ArrayList<String>();
        for (String str : midExpressionList) {
            if(str.matches("\\d+")){
                //是一个或多个数字, 就存入resList
                resList.add(str);
            }else if (str.equals("(")){
                //如果是 左括号 , 就加入cal  栈
                cal.push(str);
            }else if(str.equals(")")){
                //如果是右括号,  此时需要将cal 栈的运算符号,依次pop,并加入到resList中, 直到遇到"左括号"停止,  最后将"左括号"删除
                while(! cal.peek().equals("(")){
                    resList.add(cal.pop());
                }
                cal.pop();//跳出循环时,已经将"("之前的运算符都存入resList中,  此一步是将"("删除
            }else {
                //是运算符 +,-,*,/  , 如果是运算符, 如果cal栈为空,直接加入栈,  如果该运算符 优先级小于等于 cal栈顶运算符, 将cal栈中运算符 依次pop,加入到resList中, 知道运算符优先级大于为止
                while(cal.size() != 0 && operator(str) <= operator(cal.peek())){
                    resList.add(cal.pop());
                }
                cal.push(str);
            }
        }
        //最后将 cal栈中的运算符依次弹出加入到resList中
        while(cal.size() != 0){
            resList.add(cal.pop());
        }
        return resList;
    }

    private static int operator(String str) {
        if(str.equals("+") || str.equals("-")){
            return 1;
        }
        if(str.equals("*") || str.equals("/")){
            return 2;
        }
        return 0;
    }


    private static void calculator(List<String> suffixExpressionList) throws Exception {
        Stack<String> stack = new Stack<>();

        for (String str : suffixExpressionList) {
            if(str.matches("\\d+")){
                //是数字, 入栈
                stack.push(str);
            }else{
                //是运算符, 从栈中pop二个数, 计算,将计算结果存入stack中, 最终stack中的数, 就是计算结果
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;

                if(str.equals("+")){
                    res = num1 + num2;
                } else if(str.equals("-")){
                    res = num1 - num2;
                } else if(str.equals("*")){
                    res = num1 * num2;
                } else if(str.equals("/")){
                    res = num1 / num2;
                } else{
                    throw new Exception("没有这个运算符:"+str);
                }
                //计算结果  入栈
                stack.push(String.valueOf(res));
            }
        }
        System.out.println("最终的计算结果为:" + stack.pop());
    }

}

测试结果:

在测试一个:

内容总结

以上是互联网集市为您收集整理的6, java数据结构和算法: 栈的应用, 逆波兰计算器, 中缀表达式--> 后缀表达式全部内容，希望文章能够帮你解决6, java数据结构和算法: 栈的应用, 逆波兰计算器, 中缀表达式--> 后缀表达式所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---