题解 | #表达式求值#

比如：-1*(-1-1) => -1 -1 1 - *

package com.ihang.learn.java.huawei;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;

/**
 * @author yaohangyang
 * @date 2022/11/7
 */
public class HJ54 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) {
            // 注意 while 处理多个 case
            System.out.println(hj54(in.nextLine()));
        }
    }

    //中缀表达式转后缀表达式
    public static Deque<String> Mid2End(String str) {
        //用于存运算数
        StringBuilder number = new StringBuilder();
        //后缀表达式
        Deque<String> deque = new LinkedList<>();
        //运算操作符
        Stack<Character> stack = new Stack<>();
        boolean flag = false;
        for(int i = 0; i<str.length(); i++){
            char c = str.charAt(i);
            if(c>='0' && c<='9'){
                number.append(c);
            }else {
                if(number.length()>0){
                    if(flag){
                        deque.add("-"+number.toString());
                        flag = false;
                    }else {
                        deque.add(number.toString());
                    }
                    number.delete(0,number.length());
                }
               if(c=='('){
                   stack.push(c);
               }else if(c==')'){
                   char top = stack.peek();
                   while (top!='('){
                       deque.add(stack.pop()+"");
                       top = stack.peek();
                   }
                   stack.pop();
               }else if(c=='-' && (i==0 || str.charAt(i-1)=='(')){
                   // 用于处理运算数是负数的情况 比如：-1*(-1-1) => -1 -1 1 - *
                   flag = true;
               }else  {
                   if(stack.size()<=0 || stack.peek()=='(' || opeCompare(c,stack.peek())){
                       stack.push(c);
                   }else {
                       while (stack.size()>0 && stack.peek()!='(' && !opeCompare(c,stack.peek())){
                           deque.add(stack.pop()+"");
                       }
                       stack.push(c);
                   }
               }
            }
        }
        if(number.length()>0){
            deque.add(number.toString());
        }
        while (stack.size()>0){
            deque.add(stack.pop()+"");
        }

        return deque;
    }

    //运算符优先级比较
    public static  boolean opeCompare(char a ,char b){
        if(a=='*' || a=='/'){
            if(b=='+' || b=='-'){
                return true;
            }
        }
        return false;
    }

    //后缀表达式计算
    public static int hj54(String str){
        Deque<String> deque = Mid2End(str);
        Stack<Integer> stack = new Stack<>();
        while (deque.size()>0){
            String s = deque.pollFirst();
            if(s.charAt(s.length()-1)>='0' && s.charAt(s.length()-1)<='9'){
                stack.push(Integer.parseInt(s));
            }else {
                int b = stack.pop();
                int a = stack.pop();
                int r = 0;
                switch (s.charAt(0)){
                    case '*':
                        r = a*b;
                        break;
                    case '/':
                        r = a/b;
                        break;
                    case '+':
                        r = a+b;
                        break;
                    case '-':
                        r = a-b;
                        break;
                    default:
                        break;
                }
                stack.push(r);
            }
        }
        return stack.pop();
    }
}