⭐ 题目日期：

快手实习 - 2024/10/24

🌳 题目描述：

字符串表达式计算，如3*(2+1)/4

🧗难度系数：

⭐️ ⭐️ ⭐ ⭐

📝思路分析：

运算优先级由高到低：

1. ()
2. * /
3. + -

() 的存在会让这道题看着特别复杂，我们先移除输入中的所有括号，简化分析思路。

以 2+3*2-1 为例，依次扫描输入的字符，将其分别加入操作数和操作符区域，

操作数：2 3

操作符：+

当访问到 c = '*', 由于操作数列表里有两个数，操作符列表里有一个操作符号，由于优先级 + 小于， 所以不能计算 +，但也无法计算乘法运算，因为乘号后面的数还没访问到，所以得把 * 先加到列表里，继续访问字符串。

操作数：2 3

操作符：+

当 c = '2', 加入操作数列表

操作数：2 3 2

操作符：+

当 c = '-', 最近加入的 * 优先级大于等于 -，计算 3*2=6，将运算结果6加入操作列表：

操作数：2 6

操作符：+

优先级 '+' >= '-'，2+6=8， 将8加入列表：

操作数：8

操作符：

将当前操作符 '-' 也加入列表：

操作数：8

操作符: -

当 c = '1', 加入操作列表：

操作数：8 1

操作符: -

字符串访问完成，最终操作符列表里所剩下的所有操作符优先级顺序为，越后加入的优先级越大。当前的例子刚好只剩一个操作符，直接计算即可：

8-1=7， 返回 7

总结一下运算规则为：

1. 遇到数字直接加到操作数列表
2. 遇到优先级，与最近加入的优先级做对比，
   1. 如果大于加入的优先级，则将操作符直接加入到操作符列表，
   2. 否则从操作列表里拿一个操作符和两个操作数进行计算，将计算的结果加到原来的列表，重复上面的操作直到找到一个比当前操作符优先级更低的操作符或者列表为空，再将当前的操作符加入到列表。

按照上面的规则，当我们引入括号时，例：2+3*(2-1)

操作数：2 3 2 1

操作符：+ * ( -

由于括号的优先级最高，我们要让括号里面的操作符最先被计算，可以将 '(' 的优先级设为最低，这样当 c = ')' 时，根据上面总结的规则，由于 '-' 的优先级比 '(' 大，所以我们优先计算 '-', 计算完，将 '(' 移除，得：

操作数：2 3 1

操作符：+ *

返回 5

💻代码：

Java

public double calculate(String expression) {
 Deque<Double> numbers = new LinkedList<>();     // 数字栈
 Deque<Character> operators = new LinkedList<>(); // 操作符栈

 int i = 0;
 while (i < expression.length()) {
     char c = expression.charAt(i);

     if (c == '(') {
         operators.push(c);
         i++;
     } else if (c == ')') {
         // 计算括号内的表达式
         while (operators.peek() != '(') {
             compute(numbers, operators);
         }
         operators.pop(); // 弹出 '('
         i++;
     } else if (isOperator(c)) {
         // 处理操作符，考虑优先级
         while (!operators.isEmpty() && precedence(operators.peek()) >= precedence(c)) {
             compute(numbers, operators);
         }
         operators.push(c);
         i++;
     } else if (Character.isDigit(c)) {
         // 解析数字
         StringBuilder sb = new StringBuilder();
         while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
             sb.append(expression.charAt(i++));
         }
         numbers.push(Double.parseDouble(sb.toString()));
     }
 }

 // 计算剩余的操作
 while (!operators.isEmpty()) {
     compute(numbers, operators);
 }

 return numbers.pop();
}

private boolean isOperator(char c) {
 return c == '+' || c == '-' || c == '*' || c == '/';
}

// 定义操作符的优先级
private int precedence(char c) {
 if (c == '+' || c == '-') {
     return 1;
 } else if (c == '*' || c == '/') {
     return 2;
 }

 return 0;
}

private void compute(Deque<Double> numbers, Deque<Character> operators) {
 if (numbers.size() < 2) {
     return;
 }
 double b = numbers.pop();
 double a = numbers.pop();
 char operator = operators.pop();
 double result = 0.0;
 switch (operator) {
     case '+':
         result = a + b;
         break;
     case '-':
         result = a - b;
         break;
     case '*':
         result = a * b;
         break;
     case '/':
         result = a / b;
         break;
     default:
         break;
 }
 numbers.push(result);
}

🚵🏻复杂度分析：

时间复杂度：O(n)

空间复杂度：O(1)