image.png

    1. package com.atguigu.stack;
    3. import java.util.ArrayList;
    4. import java.util.List;
    5. import java.util.Stack;
    7. /**
    8.  * @author Dxkstart
    9.  * @create 2021-10-08-19:49
    10.  */
    11. public class PolandNotation {
    12.     public static void main(String[] args) {
    13.         //先定义一个逆波兰表达式
    14.         //(3+4)*5-6 => 3 4 + 5 * 6 -
    15.         String suffixExpression = "3 4 + 5 * 6 -";
    16.         //思路
    17.         //1.先将 "3 4 + 5 * 6 -" => 放到ArrayList中
    18.         //2.将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算
    20.         List<String> rpnList = getListString(suffixExpression);
    22.         System.out.println("计算结果为：" + calculate(rpnList));
    24.     }
    26.     //将一个逆波兰表达式，依次将数据和运算符放入到ArrayList中
    27.     public static List<String> getListString(String suffixExpression) {
    28.         //将sufferExpression 分割
    29.         String[] split = suffixExpression.split(" ");
    30.         List<String> list = new ArrayList<>();
    31.         for (String str : split) {
    32.             list.add(str);
    33.         }
    34.         return list;
    35.     }
    37.     //完成对逆波兰表达式的运算
    38.     /*
    39.     1.从左至右扫描，将3和4压入堆栈
    40.     2.遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈
    41.     3.将5入栈
    42.     4.接下来是×运算符，因此弹出5和7，计算出7*5=35，将35入栈
    43.     5.将6入栈
    44.     6.最后是-运算符，计算出35-6的值，即29，由此得出最终结果
    46.      */
    47.     public static int calculate(List<String> ls) {
    48.         int val;
    49.         int num2;
    50.         int num1;
    51.         //创建一个栈，只需要一个就可以
    52.         Stack<String> stack = new Stack<>();
    53.         //遍历ls
    54.         for (String item : ls) {
    55.             //这里用正则表达式来判断取出来的是数字还是符号
    56.             if (item.matches("\\d+")) { //匹配的是多位数
    57.                 //入栈
    58.                 stack.push(item);
    59.             } else {
    60.                 //pop出两个数，并运算，再将结果入栈
    61.                 num2 = Integer.parseInt(stack.pop());
    62.                 num1 = Integer.parseInt(stack.pop());
    63.                 if (item.equals("+")) {
    64.                     val = num1 + num2;
    65.                 } else if (item.equals("-")) {
    66.                     val = num1 - num2;
    67.                 } else if (item.equals("*")) {
    68.                     val = num1 * num2;
    69.                 } else if (item.equals("/")) {
    70.                     val = num1 / num2;
    71.                 } else {
    72.                     throw new RuntimeException("运算符有误！");
    73.                 }
    74.                 //把val入栈
    75.                 stack.push(Integer.toString(val));
    76.             }
    77.         }
    78.         return Integer.parseInt(stack.pop());
    79.     }
    81. }