227. 基本计算器 II

2023-05-14 16:54 力扣 阅94

找不到原题了，在leetcode找到类似的题目，不过leetcode的题目上没有括号的要求，代码实现中是有括号的。

题目：https://leetcode.cn/problems/basic-calculator-ii/

代码：

折叠复制代码
  1. public class Solution {
  2.     private static final Character add = '+';
  3.     private static final Character sub = '-';
  4.     private static final Character mult = '*';
  5.     private static final Character divi = '/';
  6.     private static final Character parenthesesLeft = '(';
  7.     private static final Character parenthesesRight = ')';
  9.     /**
  10.      * 符号map key为计算符号 value为优先级
  11.      */
  12.     private static final Map<Character, Integer> symbolMap = new HashMap<>();
  14.     static {
  15.         symbolMap.put(add, 0);
  16.         symbolMap.put(sub, 0);
  17.         symbolMap.put(mult, 1);
  18.         symbolMap.put(divi, 1);
  19.         symbolMap.put(parenthesesLeft, 2);
  20.         symbolMap.put(parenthesesRight, 2);
  21.     }
  23.     public int calculate(String s) {
  24.         List<Object> expressionList = this.parseExpression(s);
  25.         System.out.println("解析后：" + expressionList);
  26.         expressionList = this.toReversePolishNotation(expressionList);
  27.         System.out.println("逆波兰式：" + expressionList);
  28.         return this.calculate(expressionList).intValue();
  29.     }
  31.     /**
  32.      * 解析表达式
  33.      *
  34.      * @param expression
  35.      * @return
  36.      */
  37.     public List<Object> parseExpression(String expression) {
  38.         List<Object> list = new ArrayList<>();
  39.         StringBuilder numStr = new StringBuilder();
  40.         //去空格
  41.         expression = expression.replaceAll(" ", "");
  42.         //遍历字符串，提取数字和计算符号
  43.         for (Character c : expression.toCharArray()) {
  44.             if (symbolMap.containsKey(c)) {
  45.                 //计算符号
  46.                 if (numStr.length() > 0) {
  47.                     //数字转Long类型
  48.                     list.add(Long.valueOf(numStr.toString()));
  49.                     numStr = new StringBuilder();
  50.                 }
  51.                 list.add(c);
  52.             } else {
  53.                 //数字
  54.                 numStr.append(c);
  55.             }
  56.         }
  57.         if (numStr.length() > 0) {
  58.             //数字转Long类型
  59.             list.add(Long.valueOf(numStr.toString()));
  60.         }
  61.         return list;
  62.     }
  64.     /**
  65.      * 转成逆波兰式（后缀表达式）
  66.      *
  67.      * @param expressionList
  68.      * @return
  69.      */
  70.     public List<Object> toReversePolishNotation(List<Object> expressionList) {
  71.         List<Object> list = new ArrayList<>();
  72.         Stack<Character> stack = new Stack<>();
  73.         //遍历表达式并转换
  74.         for (Object item : expressionList) {
  75.             if (symbolMap.containsKey(item)) {
  76.                 //计算符号
  77.                 if (parenthesesLeft.equals(item)) {
  78.                     //左括号入栈
  79.                     stack.push((Character) item);
  80.                 } else if (parenthesesRight.equals(item)) {
  81.                     //右括号，出栈直到碰到左括号
  82.                     while (!stack.isEmpty() && !parenthesesLeft.equals(stack.peek())) {
  83.                         list.add(stack.pop());
  84.                     }
  85.                     //将左括号弹出丢弃
  86.                     if (!stack.isEmpty()) {
  87.                         stack.pop();
  88.                     }
  89.                 } else {
  90.                     //其他符号，当前符号的优先等级小于栈内的，将栈内的全部出栈
  91.                     while (!stack.isEmpty() && !parenthesesLeft.equals(stack.peek()) && symbolMap.get(item) <= symbolMap.get(stack.peek())) {
  92.                         list.add(stack.pop());
  93.                     }
  94.                     //将当前符号入栈
  95.                     stack.push((Character) item);
  96.                 }
  97.             } else {
  98.                 //数字
  99.                 list.add(item);
  100.             }
  101.         }
  102.         //清空栈
  103.         while (!stack.isEmpty()) {
  104.             list.add(stack.pop());
  105.         }
  106.         return list;
  107.     }
  109.     /**
  110.      * 通过逆波兰式进行计算
  111.      *
  112.      * @param expressionList
  113.      * @return
  114.      */
  115.     public Long calculate(List<Object> expressionList) {
  116.         Stack<Long> stack = new Stack<>();
  117.         for (Object item : expressionList) {
  118.             if (symbolMap.containsKey(item)) {
  119.                 //计算符号
  120.                 Long num2 = stack.pop();
  121.                 Long num1 = stack.pop();
  122.                 if (add.equals(item)) {
  123.                     stack.push(num1 + num2);
  124.                 } else if (sub.equals(item)) {
  125.                     stack.push(num1 - num2);
  126.                 } else if (mult.equals(item)) {
  127.                     stack.push(num1 * num2);
  128.                 } else if (divi.equals(item)) {
  129.                     stack.push(num1 / num2);
  130.                 }
  131.             } else {
  132.                 //数字
  133.                 stack.push((Long) item);
  134.             }
  135.         }
  136.         return stack.pop();
  137.     }
  139. }

思路：分三步走
1、先解析整个字符串，主要是拆出数字和计算符号，因为数字是Long类型，符号是String类型，简单操作就直接用一个List<Object>类型的list接数据。
实现上比较简单，提前将计算符号用一个Map存起来（Set也可以，不过后续有需要用到计算符号的优先级，所以用Map），使用StringBuilder拼接数字，如果遇到计算符号或者字符串都读完了，就把StringBuilder的值转成Long类型数字。

2、使用逆波兰式（后缀表达式）的方法来做计算，逆波兰式相关的资料见：https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437 。
这是整个题目实现上最复杂的部分，主要是用到了Stack栈，通过符号的一个优先级（括号由于比较特殊，优先级最高，所以直接if中特殊处理的），来判断出栈或者清空Stack的时机，具体请看代码注释。

3、通过逆波兰式进行计算。
这个比较简单，还是使用到Stack栈，如果是数字就入栈，碰到计算符号就弹出前2个值，也就是出栈。然后根据计算符号的规则（加减乘除）计算后将结果再次入栈。最终栈内有且只会有一个数字，也就是答案。

觉得内容还不错？打赏个钢镚鼓励鼓励！！👍