题解 | #表达式求值#

import java.util.*;

public class Solution {
    //主要思路 栈s1存左括号、运算符 栈s2存数字 利用括号匹配来进行运算
    //设置优先级
    Map<Character, Integer> map = new HashMap<Character, Integer>() {
        {
            put('-', 1);
            put('+', 1);
            put('*', 2);
            put('/', 2);
            put('%', 2);
            put('^', 3);
        }
    };
    int index = 0; //index 指向当前String中的字符

    //利用栈1的运算符和栈2的数字 进行运算
    public void getSum(Deque<Character> s1, Deque<Integer> s2) {
        if (s1.isEmpty()) return;
        if (s2.isEmpty() || s2.size() < 2) return;
        int sum = 0;
        char tempChar = s1.pollLast();
        int a = s2.pollLast();
        int b = s2.pollLast();
        switch (tempChar) {
            case '+':
                sum = a + b;
                break;
            case '-':
                sum = b - a;
                break;
            case '*':
                sum = a * b;
                break;
            case '/':
                sum = a / b;
                break;
        }
        s2.addLast(sum);//运算后得到的结果sum要压入栈2中
    }

    //通过字符串得到数字
    public void getInt(Deque<Integer> s2, String s) {
        if (s.charAt(index) >= '0' && s.charAt(index) <= '9') {
            int j = index;
            int tempInt = 0;
            while (j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9') {
                tempInt = tempInt * 10 + s.charAt(j) - '0';
                j++;
            }
            s2.addLast(tempInt);
            index = j - 1;
        }
    }

    //判断当前字符是否是数字字符
    public boolean isNumber(char c) {
        return Character.isDigit(c);//用于判断当前字符是否是数字字符
    }

    public int solve(String s) {
        //左括号和运算符加入栈1中
        //数字加入到栈2中
        //如果栈1匹配到右括号那么弹出一个运算符 然后栈2弹出两个数字 进行运算 直到栈1的顶是左括号停止
        //这里ArrayDeque可以当栈或者双端队列来用 并且它的效率更高
        Deque<Character> s1 = new ArrayDeque<>();
        Deque<Integer> s2 = new ArrayDeque<>();
        while (index < s.length()) { //"(2*(3-4))*5"
            if (s.charAt(index) == '(') { //匹配到左括号
                s1.addLast(s.charAt(index));
                index++;
            } else if (s.charAt(index) == ')') { //匹配到右括号
                while (!s1.isEmpty()) {
                    if (s1.peekLast() != '(') { //如果s1栈顶不是左括号
                        getSum(s1, s2); //那么就进行运算
                    } else { //直到遇到第一个左括号的时候 左括号弹出栈1 break;
                        s1.pollLast();
                        break;
                    }
                }
                index++;//同时往后继续找字符
            } else { //匹配到其他字符
                if (isNumber(s.charAt(index))) { //匹配到是数字字符
                    getInt(s2, s); //得到数字 并把它压入栈2中
                    index++;//同时往后继续找字符
                } else { //匹配到运算符
                    while (!s1.isEmpty() && s1.peekLast() != '(') {
                        char prev = s1.peekLast(); //把s1的栈顶元素先给prev
                        if (map.get(prev) >= map.get(s.charAt(index))) { //进行判断优先级
                            //如果当前运算符优先级比prev的优先级低
                            getSum(s1, s2); //那就把之前的运算符和数字先进行计算
                        } else { //如果优先级不小 那么出循环
                            break;
                        }
                    }
                    s1.addLast(s.charAt(index));//压入栈s1;
                    index++;//同时往后继续找字符
                }
            }
        }
        while (!s1.isEmpty() && s1.peekLast() != '(') getSum(s1, s2); //如果栈s1仍然有元素并且栈顶元素不是左括号 那么就进行运算;
        return s2.peekLast();//最后得到的s2栈只有一个数字就是运算后的结果
    }
}