力扣面试150 基本计算器 双栈模拟

Problem: 224. 基本计算器

👨‍🏫 参考题解

Code

class Solution {public int calculate(String s) {// 存放所有的数字，用于计算LinkedList<Integer> nums = new LinkedList<>();// 为了防止第一个数为负数，先往 nums 中加个 0nums.add(0);// 去掉表达式中的所有空格s = s.replaceAll(" ", "");// 存放所有的操作符，包括 +、-、(、)LinkedList<Character> ops = new LinkedList<>();int n = s.length(); // 获取表达式的长度char[] cs = s.toCharArray(); // 将字符串转换为字符数组，方便逐字符处理// 遍历整个表达式for (int i = 0; i < n; i++) {char c = cs[i];if (c == '(') {// 如果当前字符是左括号 '('，则将其压入 ops 栈中ops.add(c);} else if (c == ')') {// 如果当前字符是右括号 ')'，则进行计算直到遇到左括号 '(' 为止while (!ops.isEmpty()) {char op = ops.peekLast();if (op != '(') {// 计算当前的操作符cal(nums, ops);} else {// 遇到左括号 '('，弹出并结束循环ops.pollLast();break;}}} else {if (isNum(c)) {// 如果当前字符是数字，则需要将整组连续的数字取出来int u = 0;int j = i;// 将从 i 位置开始后面的连续数字整体取出，加入 nums 中while (j < n && isNum(cs[j])) {u = u * 10 + (int) (cs[j++] - '0');}nums.addLast(u);// 更新 i 到数字串的最后一位i = j - 1;} else {// 如果是运算符，首先处理一元运算符的情况，例如 -(2+3)if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {// 如果当前字符前是左括号 '(' 或 '+' 或 '-'，则认为是一个一元操作符，将 0 压入 numsnums.addLast(0);}// 在添加新操作符之前，先计算掉 ops 栈中所有的前导操作符（按照顺序）while (!ops.isEmpty() && ops.peekLast() != '(') {cal(nums, ops);}// 将当前操作符加入 ops 栈ops.addLast(c);}}}// 如果表达式遍历完毕，仍有操作符残留在 ops 栈中，继续进行计算while (!ops.isEmpty()) {cal(nums, ops);}// 最终结果是 nums 栈的最后一个值return nums.peekLast();}// 计算 nums 栈顶的两个数，并根据 ops 栈顶的操作符进行加减运算private void cal(LinkedList<Integer> nums, LinkedList<Character> ops) {if (nums.isEmpty() || nums.size() < 2) return;if (ops.isEmpty()) return;// 取出 nums 栈顶的两个数int b = nums.pollLast();int a = nums.pollLast();// 取出 ops 栈顶的操作符char op = ops.pollLast();// 根据操作符进行相应的计算nums.addLast(op == '+' ? a + b : a - b);}// 判断字符是否为数字boolean isNum(char c) {return Character.isDigit(c);}
}