题解 | #表达式求值#

import java.util.*;


public class Solution {
       Map<Character,Integer> map = new HashMap<>();
    
    public int solve (String s) {
        map.put('+',1);
        map.put('-',1);
        map.put('*',2);
        map.put('(',3);
        map.put(')',3);
        return compute(toSuffix(s));
    }
    
    boolean isNumber(char c){
        return c <='9' && c >= '0';
    }
    
    
    String toSuffix(String s){
        Deque<Character> stack = new LinkedList<>();
        int i = 0;
        StringBuilder ret = new StringBuilder();
        while(i < s.length()){
            if(isNumber(s.charAt(i))){
                int begin = i;
                while(i < s.length() && isNumber(s.charAt(i))) i++;
                ret.append(s.substring(begin,i)).append(' '); // 区分数字!
                i--;
            }else if(s.charAt(i) == '('){
                stack.push('(');
            }else if(s.charAt(i) == ')'){
                while(!stack.isEmpty() && stack.peek() != '('){
                    ret.append(stack.pop());
                }
                // 去掉左括号!
                stack.pop();
            }else {
                if(stack.isEmpty()) stack.push(s.charAt(i));
                else {
                    while(!stack.isEmpty() && map.get(s.charAt(i)) <= map.get(stack.peek())){
                    	if(stack.peek() == '(') break;
                        ret.append(stack.pop());
                    }
                    stack.push(s.charAt(i));
                }
            }
            i++;
        }
        
        while(!stack.isEmpty()) ret.append(stack.pop());
        
        return ret.toString();
    }
    
    int compute(String s){
        Deque<String> stack = new LinkedList<>();
        int i = 0;
        while(i < s.length()){
            if(isNumber(s.charAt(i))){
                int begin = i;
                while(i < s.length() && isNumber(s.charAt(i))){
                    i++;
                }
                stack.push(s.substring(begin,i));
                i--;
            }else if(s.charAt(i) != ' ') {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                switch(s.charAt(i)){
                    case '+': num2 += num1;  break;
                    case '-': num2 -= num1;  break;
                    case '*': num2 *= num1;  break;
                }
                stack.push(String.valueOf(num2));
            }
            i++;
        }
        return Integer.parseInt(stack.pop());
    }
    
}