题解 | #表达式求值#
表达式求值
https://www.nowcoder.com/practice/c215ba61c8b1443b996351df929dc4d4
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 返回表达式的值 * @param s string字符串 待计算的表达式 * @return int整型 */ //使用map维护一个运算符优先级 Map<Character, Integer> map = new HashMap<Character, Integer>() { { put('+', 1); put('-', 1); put('*', 2); } }; public int solve(String s) { //去掉字符串中的空格 String str = s.replaceAll(" ", ""); char[] chars = str.toCharArray(); int len = str.length(); //存放操作数 Deque<Integer> nums = new ArrayDeque<>(); //以防第一个数是负数,首先在nums里加入0; 减少边界判断 nums.push(0); //存放运算符及括号 Deque<Character> ops = new ArrayDeque<>(); for (int i = 0; i < len; i++) { char c = chars[i]; //如果是"("直接加入ops if (c == '(') { ops.push(c); } else if (c == ')') { //遇到")"ops持续出栈直到遇到"(" while (!ops.isEmpty()) { if (ops.peek() != '(') { calc(nums, ops); } else { ops.pop(); break; } } } else if (isNumber(c)) { int k = 0; int j = i; // 将从 i 位置开始后面的连续数字整体取出,加入 nums while (j < len && isNumber(chars[j])) { k = 10 * k + (chars[j++]-'0'); } nums.push(k); i = j - 1; } else { //(-i+j)>>>(0-i+j) if (i > 0 && (chars[i - 1] == '(' || chars[i - 1] == '+' || chars[i - 1] == '-')) { nums.push(0); } // 只有满足「栈内运算符」比「当前运算符」优先级高/同等,才进行运算 while (!ops.isEmpty() && ops.peek() != '(') { char pre = ops.peek(); if (map.get(pre) >= map.get(c)) { calc(nums, ops); } else { break; } } ops.push(c); } } // 将剩余的计算完 针对最后栈中只剩一个非"("的操作符 例i*j while (!ops.isEmpty()&& ops.peekLast() != '(') { calc(nums, ops); } //下方加注释针对空字符串有空指针异常 //return nums.pop(); return nums.peek(); } private boolean isNumber(char c) { return Character.isDigit(c); } // 计算逻辑:从 nums 中取出两个操作数,从 ops 中取出运算符,然后根据运算符进行计算 private void calc(Deque<Integer> nums, Deque<Character> ops) { if (nums.isEmpty() || nums.size() < 2) return; if (ops.isEmpty()) return; int b = nums.pop(); int a = nums.pop(); char c = ops.pop(); int k = 0; if (c == '+') k = a + b; else if (c == '-') k = a - b; else if (c == '*') k = a * b; nums.push(k); } }