题解 | #表达式求值#

import java.util.*;


public class Solution {
    
    public int solve (String s) {
        Map<Character,Integer> map = new HashMap<>();
        map.put('-',1);
        map.put('+',1);
        map.put('*',2);
        map.put('/',2);
        // write code here
        // 存放运算符,(直接进入栈，继续遍历字符串，遇到）时
        // 就开始进行数字出栈，运算符出栈进行运算
        // 直到栈为空或者遇到另一个（
        Deque<Character> s2 = new LinkedList<>();
        // 存放数
        Deque<Integer> s1 = new LinkedList<>();
        s = "(" +s+")";//这样使栈1最后一个元素就是结果
        int i=0;
        while(i<s.length()){

            if(s.charAt(i)<='9'&&s.charAt(i)>='0'){
                int num=0;
                //转换成数字
                while(Character.isDigit(s.charAt(i))){
                    num = num*10 + s.charAt(i)-'0';
                    i++;
                }
                i--;
                s1.push(num);
            }else  if(s.charAt(i)=='('){
                s2.push('(');

            }else if(s.charAt(i)=='-'||s.charAt(i)=='+'||s.charAt(i)=='*'||s.charAt(i)=='/'){
                // 当遇到运算符时，判断是否优先级大于当前s2的栈顶元素，
                // 小于就进行运算，大于就进栈
                if(!s2.isEmpty()&& map.containsKey(s2.peek())&&map.get(s.charAt(i))<=map.get(s2.peek())){
                    // 注意此处如果是-号的话要注意减的顺序
                    int b = s1.pop();
                    int a = s1.pop();
                    char c= s2.pop();
                    int d = operation(a,b,c); 
                    s1.push(d);
                }
                //大于直接入栈
                s2.push(s.charAt(i));
            }else {
                // 遇到右括号时，出栈进行计算，直到栈为空或者遇到（
                while(!s2.isEmpty()&&s2.peek()!='('){
                    // 此处也要注意a，b顺序以免相减出错
                    int b = s1.pop();
                    int a = s1.pop();
                    char c= s2.pop();
                    int d = operation(a,b,c);
                    //结果入栈
                    s1.push(d);

                }
                //栈2弹出第一次遇到的左括号，第一次括号内运算结束
                s2.pop();
            }
            i++;
        }
        

        return s1.pop();
    }

    // 进行运算，
    public int operation(int a,int b,char ch){
        if(ch=='-') return a-b;
        if(ch=='+') return a+b;
        if(ch=='*') return a*b;
        return a/b;
    }
}