题解 | #表达式求值#

//整体思路：
//https://blog.csdn.net/Amentos/article/details/127182926?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522171747048816800182783010%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=171747048816800182783010&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-127182926-null-null.142^v100^pc_search_result_base3&utm_term=%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F&spm=1018.2226.3001.4187
//上述博客有中缀表达式和后缀表达式的讲解，可以了解具体概念，并且如何计算后缀表达式也有相关说明
//下面开始傻瓜式代码，保证你一定看的懂！
import java.util.*;

public class Solution {

    public Map<Character, Integer> map = new HashMap<>();
    
    public void operateMap(){
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);
        map.put('(', 0);
    }
    
    public int solve (String s) {
        if (s == ""){
            return 0;
        }

        operateMap();
        return calculate(houzhui(s));
    }
    

    //中缀表达式转换为后缀表达式
    public String houzhui(String s){
        //用来临时存放运算符
        Stack<Character> opt = new Stack<>();
        //用来存放后缀表达式
        String res = "";

        for(int i = 0; i < s.length(); i++){
            //将遍历的每一个字符都取出来
            char c = s.charAt(i);
            if (c == ' '){
                continue;
            }
            //如果是数字
            if (c >= '0' && c <= '9'){
                while(i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9'){
                    res += s.charAt(i);
                    i++;
                }
                res += "#";
                i--;
            }
            //左括号直接入栈
            else if (c == '('){
                opt.add(c);
            }
            //右括号依次从opt栈顶退运算符，直至碰到左括号
            else if (c == ')'){
                while(opt.size() != 0 && opt.peek() != '('){
                    res += opt.pop();
                }
                //这里暂时不考虑违法操作
                //将左括号弹出
                opt.pop();
            }
            //运算符分情况讨论
            else{
                //首先讨论负数的符号问题，需要将负号和运算符的减号逻辑上划等号
                //负号单独出现的情况只有这两种，要么开头要么和左括号连在一起，不考虑违法操作,
                //例如：5*-5，都认为符合正常书写规范，类似5*(-5)
                if (c == '-' && (i == 0 || s.charAt(i - 1) == '(')){
                    res += "0";
                    res += "#";
                    //此时的负数所带的负号要想逻辑上和减号划等号，需要它的负号优先级最大，直接入栈
                    //5 / (-6 * 3)
                    //5 / ((0 - 6) * 3)
                    opt.add(c);
                    continue;
                }
                //运算符栈为空 或 栈顶是左括号 或 当前运算符的优先级大于栈顶运算符的优先级，当前运算符直接入栈
                if (opt.size() == 0 || opt.peek() == '(' || map.get(c) > map.get(opt.peek())){
                    opt.add(c);
                }
                //当当前运算符优先级小于等于栈顶运算符优先级时，一直弹出栈顶运算符直至当前运算符优先级大于栈顶运算符优先级或者栈为空
                else{
                    res += Character.toString(opt.pop());
                    //即便弹出之后，当前栈顶符号是左括号也没有关系，根据全局变量map宏定义：左括号的优先级最小
                    while (opt.size() != 0 && map.get(c) <= map.get(opt.peek())){
                        res += opt.pop();
                    }
                    opt.add(c);
                }
            }
        }

        while(opt.size() != 0){
            res += opt.pop();
        }

        return res;
    }
    
    //计算后缀表达式
    public int calculate(String s){
        //用来临时存放操作数
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9'){
                int sum = 0;
                while(s.charAt(i) != '#'){
                    sum = sum * 10 + s.charAt(i) - '0';
                    i++;
                }
                stack.add(sum);
            }
            else{
                if (c == '+'){
                    int hou = stack.pop();
                    int qian = stack.pop();
                    stack.add(qian + hou);
                }
			    //注意运算顺序
                else if (c == '-'){
                    int hou = stack.pop();
                    int qian = stack.pop();
                    stack.add(qian - hou);
                }
                else if (c == '*'){
                    int hou = stack.pop();
                    int qian = stack.pop();
                    stack.add(qian * hou);
                }
                else {
                    int hou = stack.pop();
                    int qian = stack.pop();
                    //此时先暂且不考虑除0的操作，毕竟此题并没有把除法运算包含进来
				    //后续题目如果有除法操作，可以选择进行if判断，return题目要求的不合法的默认值
                    stack.add(qian / hou);
                }
            }
        }
        return stack.pop();
    }
}