题解 | #表达式求值# 两个栈分别保存数值和运算符

表达式求值

https://www.nowcoder.com/practice/9566499a2e1546c0a257e885dfdbf30d

题解思路：感觉处理这种题一定要先弄明白算术运算的逻辑，包括对负数和括号的处理。如果了解中缀表达式如何转后缀表达式，那处理这个问题的思路就很清晰了。难点是对于负数的处理。我的解决方法是：定义两个栈，分别用于保存数值和运算符。保存数值时需要对负数进行判断。保存运算符时，只有当运算符栈的栈顶为* 或 / 的时候再出栈处理，先处理乘除再处理加减。遇到左括号时，直接入栈即可，只有当遇到右括号再出栈处理。写的很仓促，也没有再优化，哪里不对的地方希望朋友们指正！

import java.io.IOException;
import java.io.InputStream;
import java.util.Scanner;
import java.util.Stack;
public class Main {
    public static void main(String[] args) throws IOException {
        InputStream in = System.in;
        Scanner scanner = new Scanner(in);
        String str = scanner.nextLine();
        int result = getEvaluation(str);
        System.out.println(result);
    }
     private static int getEvaluation(String str) {
        if (str == null || str.length() == 0) return 0;
        // 记录数值
        Stack<Integer> arithmetic = new Stack<>();
        // 记录运算符
        Stack<Character> operator = new Stack<>();
        int i = 0;
        while(i < str.length()) {
            // 处理负数
            boolean negative = false;
            if ((str.charAt(i) == '-' && arithmetic.isEmpty()) ||
                    (str.charAt(i) == '-' && !(str.charAt(i-1) >= '0' && str.charAt(i-1) <= '9') && str.charAt(i-1) != ')')) {
                negative = true;
                i++;
            }
            // 保存数值
            if (i < str.length() && str.charAt(i)  >= '0' && str.charAt(i) <= '9'){
                StringBuilder builder = new StringBuilder();
                while (i < str.length() && str.charAt(i)  >= '0' && str.charAt(i) <= '9'){
                    builder.append(str.charAt(i));
                    i++;
                }
                arithmetic.push(negative ? -Integer.valueOf(builder.toString()) : Integer.valueOf(builder.toString()));
            }
            // 出栈处理数值
            if (i < str.length() && (str.charAt(i) == '+' || str.charAt(i) == '-')) {
                while (!operator.isEmpty() && (operator.peek() == '*' || operator.peek() == '/')) {
                    Character op = operator.pop();
                    Integer n1 = arithmetic.pop();
                    Integer n2 = arithmetic.pop();
                    arithmetic.push(operation(n2, n1, op));
                }
                while (!operator.isEmpty() && (operator.peek() == '+' || operator.peek() == '-')){
                        Character op = operator.pop();
                        Integer n1 = arithmetic.pop();
                        Integer n2 = arithmetic.pop();
                        arithmetic.push(operation(n2, n1, op));
                    }
                operator.push(str.charAt(i));
                i++;
            }
            // 遇到右括号再出栈处理
            else if (i < str.length() && (str.charAt(i) == ')')){
               while (true){
                   Character op = operator.pop();
                   if (op == '(') break;
                   Integer n1 = arithmetic.pop();
                   Integer n2 = arithmetic.pop();
                   arithmetic.push(operation(n2,n1,op));
               }
               i++;
            }
            // 运算符入栈
            else{
                if (i == str.length())
                    break;
                operator.push(str.charAt(i));
                i++;
            }
        }
        while (!operator.isEmpty()){
            Character op = operator.pop();
            Integer n1 = arithmetic.pop();
            Integer n2 = arithmetic.pop();
            arithmetic.push(operation(n2,n1,op));
        }
        return arithmetic.pop();
    }

    /**
     * 基础运算
     */
    private static Integer operation(Integer n1, Integer n2, Character op) {
        if (op == '+')
            return n1 + n2;
        else if (op == '-')
            return n1 - n2;
        else if (op == '*')
            return n1 * n2;
        else
            return n1 / n2;
    }
}

#笔试刷题##华为OD#