题解 | #表达式求值#

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);
        }
    }
}