题解 | #表达式求值#
表达式求值
https://www.nowcoder.com/practice/c215ba61c8b1443b996351df929dc4d4
import java.util.*; /** 1. 遍历字符串 ,对字符串每个字符进行判断 (要么是数字,要么是括号,要么是运算符,各个情况该有什么逻辑) 2. 编辑最小单元运算,封装成方法让相应的逻辑去调用 */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 返回表达式的值 * @param s string字符串 待计算的表达式 * @return int整型 */ public int solve (String s) { // 存放优先级 Map<Character, Integer> map = new HashMap<Character, Integer> (); map.put('+', 1); map.put('-', 1); map.put('*', 2); //放数字 Stack<Integer> nums = new Stack<Integer>(); //放数字和括号 Stack<Character> ops = new Stack<Character>(); //2. 遍历输入的字符串 int num = s.length(); char[] ss = s.toCharArray(); for (int i = 0 ; i < num; i++) { char ch = ss[i]; //2.1 判断数字 if (isNumber(ch)) { int temp = 0; int j = i; //2.1.1 得到一个完整的数字,并将完整数字放入数字栈 while (j < num && isNumber(ss[j])) { temp = temp * 10 + (ss[j] - '0'); j++; } nums.push(temp); i = j - 1; //2.3 考虑括号的情况,括号放入栈 } else if (ch == '(') { ops.push(ch); //2.3.1 遇到右括号,开始计算括号内, } else if (ch == ')') { while (ops.peek() != '(') { calcu(nums, ops); } // 算完整个()内的值后,去掉左括号 ops.pop(); //2.2 放运算符 } else { //按照符号优先级进行计算,先算*这种优先级高的, eg: 1+2*3+4 //包括了再括号内的* 也会先算 if (!ops.isEmpty() && ops.peek() != '(' && (map.get(ops.peek()) >= map.get(ch))) { calcu(nums, ops); } //所有符号都要放进来,不管优先级怎样,否则会漏 ops.push(ch); } } // 3.0 计算最后结果 while (!ops.isEmpty()) { calcu(nums, ops); } return nums.pop(); } public boolean isNumber (char a) { return Character.isDigit(a); } //1. 最小单元的数字和运算符计算(不需要返回值,算好后都会放入栈中) public void calcu (Stack<Integer> nums, Stack<Character> ops) { int num1 = nums.pop(); int num2 = nums.pop(); char op = ops.pop(); if (op == '+') { nums.push(num1 + num2); } else if (op == '-') { nums.push(num2 - num1) ; } else if (op == '*') { nums.push(num1 * num2); } } }