2023-09-22  阅读(199)
原文作者:李林超 原文地址: https://www.lilinchao.com/archives/501.html

完成一个逆波兰计算器,要求完成如下任务:

    (1)输入一个逆波兰表达式(后缀表达式),使用栈 (Stack),计算其结果
    (2)支持小括号和多位数整数,因为这里我们主要讲的是数据结构,因此计算器进行简化,只支持对整数的计算。

思路分析:

例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下 : > > (1). 从左至右扫描,将3和4压入堆栈; > > (2). 遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素),计算出3+4的值,得7,再将7入栈; > > (3). 将5入栈; > > (4). 接下来是×运算符,因此弹出5和7,计算出7×5=35,将35入栈; > > (5). 将6入栈; > > (6). 最后是-运算符,计算出35-6的值,即29,由此得出最终结果

代码

    public class PolandNotation {
        public static void main(String[] args) {
    
            String suffixExpression="4 5 * 8 - 60 + 8 2 / +";
            List<String> list = getListString(suffixExpression);
            int res = calculate(list);
            System.out.println("计算的结果是="+res);
        }
    
        //将一个逆波兰表达式,依次将数据和运算符放入到ArrayList中
        public static List<String> getListString(String suffixExpression){
            //将 suffixExpression分割
            String[] split = suffixExpression.split(" ");
            List<String> list = new ArrayList<String>();
            for(String ele:split){
                list.add(ele);
            }
            return list;
        }
        //完成对逆波兰表达式的运算
        /**
         * (1). 从左至右扫描,将3和4压入堆栈;
         * (2). 遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素),计算出3+4的值,得7,再将7入栈;
         * (3). 将5入栈;
         * (4). 接下来是×运算符,因此弹出5和7,计算出7×5=35,将35入栈;
         * (5). 将6入栈;
         * (6). 最后是-运算符,计算出35-6的值,即29,由此得出最终结果
         * */
        public static int calculate(List<String> ls){
            //创建一个栈,只需要一个栈即可
            Stack<String> stack = new Stack<String>();
            //遍历ls
            for(String item:ls){
                //这里使用正则表达式来取出数
                if(item.matches("\\d+")){//匹配的是多位数
                    //入栈
                    stack.push(item);
                }else{
                    //pop出两个数,并运算,再入栈
                    int num2 = Integer.parseInt(stack.pop());
                    int num1 = Integer.parseInt(stack.pop());
                    int res = 0;
                    if(item.equals("+")){
                        res = num1 + num2;
                    }else if(item.equals("-")){
                        res = num1 - num2;
                    }else if(item.equals("*")){
                        res = num1 * num2;
                    }else if(item.equals("/")){
                        res = num1 / num2;
                    }else{
                        throw new RuntimeException("运算符有误");
                    }
                    //把res入栈
                    stack.push(""+res);
                }
            }
            //最后溜在stack中的数据是运算结果
            return Integer.parseInt(stack.pop());
        }
    }

运行结果

    计算的结果是=76
阅读全文
  • 点赞