题解 | #表达式求值#

import java.util.LinkedList;
import java.util.Stack;
import java.util.HashMap;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        char[] chs = s.toCharArray(); // 将字符串转换为字符数组
        LinkedList<Object> infixQueue = new LinkedList<>(); // 中缀表达式
        LinkedList<Object> suffixQueue = new LinkedList<>(); // 后缀表达式
        Stack<Object> operatosStack = new Stack<>(); // 运算符
        Stack<Integer> numberStack = new Stack<>(); // 数字
        String val = ""; // 存放临时数据
        HashMap<Object, Integer> hm = new HashMap<>(); // 标明对象是数字还是运算符(0: 数字 1: 运算符)
        // 构造中缀表达式
        for (int i = 0; i < chs.length; i++) {
            // 获取一个字符，判断该字符是数字还是运算符
            if ((chs[i] - '0') < 0) { // 字符
                if (val.length() > 0) { // 证明 val 中存放了一个完整的整数
                    hm.put(val, 0);
                    infixQueue.add(val);
                    val = ""; // 别忘了初始化为空字符串
                }
                if (chs[i] == '+' || chs[i] == '-') {
                    hm.put(chs[i], 2);
                }
                else {
                    hm.put(chs[i], 3);
                }
                infixQueue.add(chs[i]);
            }
            else { // 数字
                val += chs[i] + "";
            }
        }
        if (0 != val.length()) {
            infixQueue.add(val); // 别忘了一个算数运算的末尾肯定是数字啊
        }
        hm.put(val, 0);
        Object ob = null; // 定义一个万能的变量
        char op = '0'; // 存放操作符
        Object tmp = null; // 辅助
        // 构造后缀表达式
        while (!infixQueue.isEmpty()) { // 不为空，就循环
            ob = infixQueue.poll(); // 获取了一个对象
            if (hm.get(ob) == 0) { // 数字
                suffixQueue.add(ob); // 直接加到后缀表达式中
            }
            else { // 运算符
                op = Character.valueOf((Character)ob);
                if ((op - '(') == 0) { // '('
                    operatosStack.push(op); // 入栈
                }
                else if ((op - ')') == 0) { // ')'
                    ob = operatosStack.pop(); // 从 operatosStack 弹出
                    while ((Character.valueOf((Character)ob) - '(') != 0) {
                        suffixQueue.add(ob); // 入 suffixQueue 队列
                        ob = operatosStack.pop(); // 继续弹出
                    }
                }
                else { // +-*
                    while (!operatosStack.isEmpty()) {
                        tmp = operatosStack.pop(); // 获取栈顶元素
                        if (Character.valueOf((Character)tmp) == '(') {
                            operatosStack.push(tmp);
                            break;
                        }
                        if (hm.get(ob) > hm.get(tmp)) { // 优先级大于栈顶元素
                            operatosStack.push(tmp);
                            break;
                        }
                        else { // 优先级不大于栈顶元素
                            suffixQueue.add(tmp); // 入 suffixQueue 队列
                        }
                    }
                    operatosStack.push(ob);
                }
            }
        }
        while (!operatosStack.empty()) { // 别忘了！！！
            suffixQueue.add(operatosStack.pop());
        }
        // 定义两个整型变量，用于存放临时数据
        int tmp1 = 0;
        int tmp2 = 0;
        while (!suffixQueue.isEmpty()) {
            ob = suffixQueue.poll(); // 获取了一个对象
            if (hm.get(ob) == 0) { // 数字
                numberStack.push(Integer.parseInt(ob.toString())); // 入栈
            }
            else { // 运算符
                op = Character.valueOf((Character)ob);
                tmp1 = numberStack.pop();
                tmp2 = numberStack.pop();
                if (op == '+') {
                    numberStack.push(tmp2 + tmp1);
                }
                else if (op == '-') {
                    numberStack.push(tmp2 - tmp1);
                }
                else if (op == '*') {
                    numberStack.push(tmp2 * tmp1);
                }
            }
        }
        return Integer.valueOf((Integer)numberStack.pop());
    }
}