题解 | #计算器(二)#

import java.util.*;

public class Solution {

//解题过程较为繁琐
public int calculate (String s) {
    // write code here
    //生成中缀表达式
    List<String> infixExpressionList = toInfixExpressionList(s);
    //生成前缀表达式
    List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
    return calculate(suffixExpressionList);
}

public List<String> toInfixExpressionList(String s){
    // 定义一个List，存放中缀表达式对应的内容
    List<String> ls = new ArrayList<>();
    int i = 0; // 这时是一个指针，用于遍历中缀表达式字符串
    String str; // 对多位数的拼接
    char c; // 每遍历一个字符，就放入到c
    do {
        // 如果c是一个非数字，我需要加入到ls
        if((c=s.charAt(i)) < 48 || (c=s.charAt(i)) > 57){
            ls.add("" + c);
            i++; // i需要后移
        } else { // 如果是一个数，需要考虑多位数
            str = ""; //先将str 置成"" '0'[48]->'9'
            while (i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57){
                str += c;//拼接
                i++;
            }
            ls.add(str);
        }
    }while (i < s.length());
    return ls; // 返回
}

public List<String> parseSuffixExpressionList(List<String> ls){
    // 定义两个栈
    Stack<String> s1 = new Stack<>(); //符号栈
    List<String> s2 = new ArrayList<>(); //存储中间结果的Lists2

    // 遍历ls
    for(String item: ls){
        // 如果是一个数，加入s2
        if (item.matches("\\d+")) {
            s2.add(item);
        } else if(item.equals("(")){
            // 如果是左括号直接加入
            s1.push(item);
        } else if(item.equals(")")){
            // 如果是右括号，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将一对括号丢弃
            while (!s1.peek().equals("(")){
                s2.add(s1.pop());
            }
            s1.pop(); // !!! 将（弹出s1栈，消除小括号
        } else {
            // 当item的优先级小于等于s1栈顶运算符，将s1栈顶的运算符弹出并加入到s2中，不断地进行比较
            // 进行优先级的比较
            while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)){
                s2.add(s1.pop());
            }
            // 还需要将item压入栈
            s1.push(item);
        }
    }
    // 将s1中剩余的运算符依次弹出并加入s2
    while(s1.size()!=0){
        s2.add(s1.pop());
    }
    return s2; // 注意因为是存放到List，因此按顺序输出就是对应的后缀表达式对应的List
}

public int calculate(List<String> ls){
    // 创建栈
    Stack<String> stack = new Stack<>();
    // 遍历ls
    for(String item: ls){
        // 这里使用正则表达式来取出数
        if(item.matches("\\d+")){ // 匹配的是多位数
            // 入栈
            stack.push(item);
        } else {
            // pop出两个数，并运算，再入栈
            int num2 = Integer.parseInt(stack.pop());
            int num1 = Integer.parseInt(stack.pop());
            int res = 0;
            if(item.equals("+")){
                res = num1 + num2;
            } else if(item.equals("-")) {
                res = num1 - num2;
            } else if(item.equals("*")) {
                res = num1 * num2;
            } else if(item.equals("/")) {
                res = num1 / num2;
            } else {
                throw new RuntimeException("运算符有误");
            }
            // 把res入栈
            stack.push("" + res);
        }
    }
    // 最后留在stack中的数据是运算结果
    return Integer.parseInt(stack.pop());
}

}

class Operation {

private static int ADD = 1;
private static int SUB = 1;
private static int MUL = 2;
private static int DIV = 2;

// 写一个方法，返回对应的优先级数字
public static int getValue(String operation){
    int result = 0;
    switch (operation) {
        case "+":
            result = ADD;
            break;
        case "-":
            result = SUB;
            break;
        case "*":
            result = MUL;
            break;
        case "/":
            result = DIV;
            break;
        default:
            System.out.println("不存在该运算符");
            break;
    }
    return result;
}

}