Java代码实现逆波兰计算器

小咪咪 2023-10-11 17:21 2阅读 0赞

关于逆波兰计算器，需求如下

*  输入一个逆波兰表达式（后缀表达式），使用栈（Stack），计算其结果，只支持对整数的计算即可。

**思路分析**

后缀表达式又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后。

例如：

( 3 + 4 ) × 5 − 6 (3+4)×5-6 (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，由此得出最终结果。

**代码实现**

import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    /**
     * @author mengzhichao
     * @create 2022-04-19-9:27
     */
    public class PolandNotation {
        
        public static void main(String[] args) {
        
            //先定义给逆波兰表达式  (3+4)*5-6 => 3 4 + 5 * 6 - 为了方便，逆波兰表达式的数字和符号使用空格隔开
            String suffixExpression = "3 4 + 5 * 6 -";
    
            //思路
            //1.先将"3 4 + 5 * 6 -"放入ArrayList中
            //2.将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算
            List<String> rpmList = getListString(suffixExpression);
            System.out.println("rpmList:"+rpmList);
    
            int res =calculate(rpmList);
            System.out.println(""+res);
        }
    
        //将一个逆波兰表达式，依次将数据和运算符，放入到ArrayList中
        public static List<String> getListString(String suffixExpression){
        
            //将 suffixExpression 分割
            String[] split = suffixExpression.split(" ");
            List<String> list =new ArrayList<>();
            for (String ele:split){
        
                list.add(ele);
            }
            return list;
        }
    
        //完成对逆波兰表达式的运算
        /**
         *     从左至右扫描，将3和4压入堆栈。
         *     遇到+运算符，弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈。
         *     将5入栈。
         *     接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈。
         *     将6入栈。
         *     最后是-运算符，计算出35-6的值，即29，由此得出最终结果。
         */
        public static int calculate(List<String> ls){
        
            //创建栈,只需要一个栈即可
            Stack<String> stack = new Stack<>();
            //遍历 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(String.valueOf(res));
                }
            }
            //最后留在stack中的数据就是运算结果
            return Integer.parseInt(stack.pop());
        }
    }

**运行并测试**

![在这里插入图片描述][56bd9df238eb4483a25c065cb96fd93f.png]

[56bd9df238eb4483a25c065cb96fd93f.png]: https://img-blog.csdnimg.cn/56bd9df238eb4483a25c065cb96fd93f.png