leetcode 227. Basic Calculator II | 227. 基本计算器 II（中缀表达式求值）

Bertha 。 2022-10-08 11:21 154阅读 0赞

## 题目 ##

[https://leetcode.com/problems/basic-calculator-ii/][https_leetcode.com_problems_basic-calculator-ii]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

这道题是 **中缀表达式求值** 的简化版（因为没有左右括号运算），不过输入的形式有两个处理起来不是那么舒服的地方：

1、题目中包含空格，造成了一些干扰，需要忽略

2、输入是一个字符串，导致数字需要拼接出来，无法直接使用 split 区分数字和运算符

##### 经典的中缀表达式求值过程如下 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

##### 本题代码 #####

import java.util.HashMap;
    import java.util.Stack;
    
    class Solution { 
        HashMap<Character, Integer> priorityMap; // 运算符优先级
    
        public int calculate(String s) { 
            initPriortyMap();
    
            char[] arr = s.toCharArray();
            Stack<Integer> s1 = new Stack<>(); // 操作数栈
            Stack<Character> s2 = new Stack<>(); // 运算符栈
    
            int cur = 0;
            for (int i = 0; i < arr.length; i++) { 
                if (arr[i] >= '0' && arr[i] <= '9') {  // 是数字
                    cur *= 10;
                    cur += arr[i] - '0';
                } else if (priorityMap.get(arr[i]) != null) {  // 是运算符
                    s1.push(cur);
                    cur = 0;
                    if (s2.isEmpty() || isPrior(arr[i], s2.peek())) {  // 若当前运算符大于栈顶运算符优先级 则入栈
                        s2.push(arr[i]);
                    } else {  // 否则 在当前运算符小于等于栈顶运算符情况下 不断出栈并运算 将运算结果入操作数栈
                        while (s2.size() > 0 && !isPrior(arr[i], s2.peek())) { 
                            Character op = s2.pop();
                            Integer n1 = s1.pop();
                            Integer n2 = s1.pop();
                            int res = cal(n1, n2, op);
                            s1.push(res);
                        }
                        s2.push(arr[i]);
                    }
                }
                if (i == arr.length - 1) s1.push(cur);
            }
            while (!s2.isEmpty()) {  // 运算符栈中还有剩余 则一直出栈并运算
                Character op = s2.pop();
                Integer n1 = s1.pop();
                Integer n2 = s1.pop();
                int res = cal(n1, n2, op);
                s1.push(res);
            }
            return s1.pop();
        }
    
        public boolean isPrior(char op1, char op2) { 
            return priorityMap.get(op1) > priorityMap.get(op2);
        }
    
        public void initPriortyMap() { 
            priorityMap = new HashMap<>(); // 运算符优先级
            priorityMap.put('+', 0);
            priorityMap.put('-', 0);
            priorityMap.put('*', 1);
            priorityMap.put('/', 1);
        }
    
        public int cal(int n1, int n2, char op) { 
            switch (op) { 
                case '+':
                    return n2 + n1;
                case '-':
                    return n2 - n1;
                case '*':
                    return n2 * n1;
                case '/':
                    return n2 / n1;
                default:
                    System.out.println("op err: " + op);
                    return -1;
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

## 官方题解 ##

针对没有左右括号的中缀表达式，官方给的题解确实比我的方法简化了很多。

但如果要改造成标准的 **包含左右括号的** 中缀表达式求值的话，我认为还是我写的上面的版本比较容易改造。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]

class Solution { 
        public int calculate(String s) { 
    
            if (s == null || s.isEmpty()) return 0;
            int len = s.length();
            Stack<Integer> stack = new Stack<Integer>();
            int currentNumber = 0;
            char operation = '+';
            for (int i = 0; i < len; i++) { 
                char currentChar = s.charAt(i);
                if (Character.isDigit(currentChar)) { 
                    currentNumber = (currentNumber * 10) + (currentChar - '0');
                }
                if (!Character.isDigit(currentChar) && !Character.isWhitespace(currentChar) || i == len - 1) { 
                    if (operation == '-') { 
                        stack.push(-currentNumber);
                    }
                    else if (operation == '+') { 
                        stack.push(currentNumber);
                    }
                    else if (operation == '*') { 
                        stack.push(stack.pop() * currentNumber);
                    }
                    else if (operation == '/') { 
                        stack.push(stack.pop() / currentNumber);
                    }
                    operation = currentChar;
                    currentNumber = 0;
                }
            }
            int result = 0;
            while (!stack.isEmpty()) { 
                result += stack.pop();
            }
            return result;
        }
    }

[https_leetcode.com_problems_basic-calculator-ii]: https://leetcode.com/problems/basic-calculator-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/26633e9d4c8244a5ac5ec7c0c5265b1f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/d8590bd4ebdf41c3a6608d884bd509ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221005/79c50ec8860e4df5b81990721310a0b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]: /images/20221005/d01b0841661f4cfa80e443bf9bf4c583.png