计算器(二)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    private HashMap<String, Integer> operation = new HashMap<>();    // 运算符优先级
    
    public int calculate (String s) {
        operation.put("+", 1);
        operation.put("-", 1);
        operation.put("*", 2);
        operation.put("/", 2);
        // 先得到逆波兰表达式
        LinkedList<String> rpn = parseSuffixExpressionList(toInfixExpressionList(s));
        // 逆波兰表达式求值
        return evalRPN(rpn);
    }
    
    private List<String> toInfixExpressionList(String express){
        List<String> list = new ArrayList<>();
        int n = express.length();
        int num = 0;
        for(int i = 0; i < n; i++){
            char c = express.charAt(i);
            if(c < '0' || c > '9'){
                list.add(String.valueOf(c));
            }else{
                num = 10 * num + (c - '0');
                if(i == n - 1 || (express.charAt(i + 1) < '0' || express.charAt(i + 1) > '9')){
                    list.add(String.valueOf(num));
                    num = 0;
                }
            }
        }
        return list;
    }
    
    private LinkedList<String> parseSuffixExpressionList(List<String> infixExpressionList){
        Stack<String> stack = new Stack<>();
        LinkedList<String> list = new LinkedList<>();
        for(String item: infixExpressionList){
            // 当item为数字时，直接加入集合
            if(isDigit(item)){
                list.add(item);
            }else if(item.equals("(")){
                // 当item为 （ 左括号时，压入栈中
                stack.push(item);
            }else if(item.equals(")")){
                // 当item为右括号时，则依次弹出stack栈顶的运算符，并加入list中，直到遇到左括号为止，此时将这一对括号丢弃
                while(!stack.peek().equals("(")){
                    list.add(stack.pop());
                }
                stack.pop();      // 将左括号丢弃
            }else{
                // 当遇到运算符时
                while(!stack.isEmpty() && operation.get(item) <= operation.get(stack.peek())){
                    list.add(stack.pop());
                }
                stack.push(item);
            }
        }
        // 将stack中的元素全部加入到list中
        while(stack.size() > 0){
            list.add(stack.pop());
        }
        return list;
    }
    
    // 计算逆波兰表达式
    private int evalRPN (LinkedList<String> tokens) {
        Stack<Integer> stack = new Stack<>();
        while(!tokens.isEmpty()) {
            String token = tokens.removeFirst();
            if(isDigit(token)){
                stack.push(Integer.parseInt(token));
            }else{
                int num1 = 0, num2 = 0;
                if(stack.size() == 1) {
                    return stack.pop();
                }else{
                    num2 = stack.pop();
                    num1 = stack.pop();
                }
                if(token.equals("+")){
                    stack.push(num1 + num2);
                }else if(token.equals("-")){
                    stack.push(num1 - num2);
                }else if(token.equals("*")){
                    stack.push(num1 * num2);
                }else if(token.equals("/")){
                    stack.push(num1 / num2);
                }
            }
        }
        return stack.pop();
    }
    
    // 判断s是否是数字
    private boolean isDigit(String s) {
        try{
            Integer.parseInt(s);
            return true;
        }catch(Exception e) {
            return false;
        }
    }
}