题解 | #表达式求值#

两个栈的方法。

比较有技巧的地方就在每次出现符号的都需要计算，计算的时候根据符号的优先级决定是否计算。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        Stack<Integer> num_stack = new Stack<>();
        Stack<Character> op_stack = new Stack<>();
        
        int result = 0;
        char op;
        for (int i = 0; i < s.length();) {
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                int m = 0;
                while(i < s.length()&&s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                    m = m * 10 + s.charAt(i) - '0';
                    i++;
                }
                // 数字直接入栈
                num_stack.push(m);
            } else if (s.charAt(i) == ')'){
                // 遇到右括号的时候需要计算到左括号为止
                i++;
                while((op = op_stack.pop()) !='(') {
                    int m1 = num_stack.pop();
                    int m2 = num_stack.pop();
                    if (op == '+') {
                        num_stack.push(m1 + m2);
                    }else if (op == '*') {
                        num_stack.push(m1 * m2);
                    } else {
                        num_stack.push(m2 - m1);
                    }
                }
            } else {
                // 如果不是左括号则进行计算
                if (s.charAt(i) != '(') {
                    calc(num_stack, op_stack, s.charAt(i));
                }
                op_stack.push(s.charAt(i));
                i++;
            }
        }
        
        while(!op_stack.isEmpty()) {
            op = op_stack.pop();
            int m1 = num_stack.pop();
            int m2 = num_stack.pop();
            if (op == '+') {
                num_stack.push(m1 + m2);
            }else if (op == '*') {
                num_stack.push(m1 * m2);
            } else {
                num_stack.push(m2 - m1);
            }
        }
        return num_stack.pop();
    }
    
    private void calc(Stack<Integer> num_stack, Stack<Character> op_stack, char op) {
        // 根据计算的优先级，+-号之前的表达式都是可以计算的
        if ((op == '+' || op == '-') && !op_stack.isEmpty()) {
            char op1 = op_stack.peek();
            if (op1 == '+') {
                op_stack.pop();
                int n1 = num_stack.pop();
                int n2 = num_stack.pop();
                num_stack.push(n1 + n2);
            } else if (op1 == '-') {
                op_stack.pop();
                int n1 = num_stack.pop();
                int n2 = num_stack.pop();
                num_stack.push(n2 - n1);
            } else if (op1 == '*') {
                op_stack.pop();
                int n1 = num_stack.pop();
                int n2 = num_stack.pop();
                num_stack.push(n2 * n1);
            }
            // 如果当前是乘则只计算前面的乘除
        } else if (op == '*' && !op_stack.isEmpty()) {
            char op1 = op_stack.peek();
            if (op1 == '*') {
                op_stack.pop();
                int n1 = num_stack.pop();
                int n2 = num_stack.pop();
                num_stack.push(n2 * n1);
            }
        }
    }
}