表达式求值

import java.util.Scanner;
import java.util.Stack;


public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String expression = in.nextLine();
        Stack<Character> s1 = new Stack<>();
        Stack<String> s2 = new Stack<>();
        String number = "";
        // 遍历表达式的每个字符，将中缀转化成后缀表达式
        for (int i = 0; i < expression.length(); i++) {
            if (isOperator(expression.charAt(i), i, expression)) {
                while (!s1.isEmpty() && s1.peek() != '(' &&
                        priorityCompare(s1.peek(), expression.charAt(i)) >= 0) {
                    s2.add(String.valueOf(s1.pop()));
                }
                s1.add(expression.charAt(i));
            } else if (expression.charAt(i) == '(') {
                s1.add(expression.charAt(i));
            } else if (expression.charAt(i) == ')') {
                while (s1.peek() != '(') {
                    s2.add(String.valueOf(s1.pop()));
                }
                s1.pop();
            } else if (Character.isDigit(expression.charAt(i))
                       || (expression.charAt(i) == '-' && (i == 0 ||
                               isNegativeNumberStart(i, expression)))) {
                // 当前字符是数字或者负号时
                number = String.valueOf(expression.charAt(i));
                for (int j = i + 1; j < expression.length(); j++) {
                    if (!Character.isDigit(expression.charAt(j))) {
                        break;
                    }
                    number = number + String.valueOf(expression.charAt(j));
                    i++;
                }
                s2.add(number);
            }
        }
        while (!s1.isEmpty()) {
            s2.add(String.valueOf(s1.pop()));
        }
        // 此时s2里就是我们已经转化好的后缀表达式，但是由于要从栈尾开始遍历，但栈只能从栈顶开始遍历，
        // 所以这里再遍历s2换到新的栈s3，此时s3的栈顶就是s2的栈尾，正常遍历s3就可以了（当然也可以使用双端栈就不用这么麻烦了）
        Stack<String> s3 = new Stack<>();
        while (!s2.isEmpty()) {
            s3.add(s2.pop());
        }
        Stack<Integer> s4 = new Stack<>();
        while (!s3.isEmpty()) {
            // 如果当前元素长度大于1，则必定是数字，比如负数-1 或 多位数11
            // 如果当前元素长度是1且isDigit==true，必定是数字
            if (s3.peek().length() > 1 || (s3.peek().length() == 1 &&
                                           Character.isDigit(s3.peek().charAt(0)))) {

                s4.add(Integer.parseInt(s3.pop()));
            } else {
                // 如果遇到运算符，则弹出栈里前两位元素进行运算
                s4.add(calculate(s4.pop(), s4.pop(), s3.pop().charAt(0)));
            }
        }
        System.out.println(s4.peek());
    }
    // 比较运算符的优先级
    public static int priorityCompare(char before, char after) {
        if (before == '+' || before == '-') {
            if (after == '*' || after == '/') {
                return -1;
            }
        } else if (before == '*' || before == '/') {
            if (after == '+' || after == '-') {
                return 1;
            }
        }
        return 0;
    }
    // 判断当前字符是否为运算符
    public static boolean isOperator(char c, int index, String expr) {
        if (c == '+' || c == '*' || c == '/') {
            return true;
        }
        // 如果是-，且不是首位，且不是负号，则说明是减号
        if (c == '-' && (index > 0 && !isNegativeNumberStart(index, expr))) {
            return true;
        }
        return false;
    }

    /**
     * 判断当前-字符是否为负号
     * @param index 当前字符的下标
     * @param expr 表达式
     * @return
     */
    public static boolean isNegativeNumberStart(int index, String expr) {
        // 如果-在首位，那么必定是负号而不是减号
        if (index == 0) {
            return true;
        }
        // 既然不是首位，那么获取前一位的字符
        char prevChar = expr.charAt(index - 1);
        // 如果前一位是以下字符则说明是负号而不是减号
        // 比如：1+(-1)、1+-1、1--1、1*-1、1/-1 这些都是负号前一位字符的特征
        return prevChar == '(' || prevChar == '+' || prevChar == '-' ||
               prevChar == '*' || prevChar == '/';
    }
    // 计算
    public static int calculate(int first, int second, char operator) {
        int result = 0;
        switch (operator) {
            case '+':
                result = first + second;
                break;
            case '-':
                // 注意这里是后一位 减去 前一位
                result = second - first;
                break;
            case '*':
                result = first * second;
                break;
            case '/':
                // 注意这里是后一位 除以 前一位
                result = second / first;
                break;
        }
        return result;
    }
}

400+5

405

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    /**
    无视左括号
    将操作数压入操作数栈
    将运算符压入运算符栈
    在遇到右括号的时候，从运算符栈中弹出一个运算符，再从操作数栈中弹出所需的操作数，
    并且将运算结果压入操作数栈中
    */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Stack<Integer> s1 = new Stack<>(); //操作数栈
        Stack<Character> s2 = new Stack<>(); //运算符栈
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            int len = str.length();
            String tem = "";
            for(int i=0; i<len; i++) {
                char ch = str.charAt(i);
                switch(ch) {
                    case '(':
                    case '[':
                    case '{':
                        break; //忽略
                    case '+':
                    case '-':
                    case '*':
                    case '/':
                        s2.push(ch);//操作符入栈
                        break;
                    case ')':
                    case ']':
                    case '}':
                        //计算，并将操作数重新入栈
                        //1.弹出操作符
                        //2.弹出操作数1
                        //3.弹出操作数2
                        //计算，并将结果重新放到操作数栈
                        char flag = s2.pop();
                        Integer num1 = s1.pop();
                        Integer num2 = s1.pop();
                        Integer sum = null;
                        switch(flag) {
                            case '+':
                                sum = num1 + num2;
                                s1.push(sum);
                                break;
                            case '-':
                                sum = num1 - num2;
                                s1.push(sum);
                                break;
                            case '*':
                                sum = num1 * num2;
                                s1.push(sum);
                                break;
                            case '/':
                                sum = num1 / num2;
                                s1.push(sum);
                                break;
                        }
                        break;
                    default:
                        tem += String.valueOf(ch);
                        if(!nextIsNotNum(str, i, len)) {
                            s1.push(Integer.parseInt(tem));
                            tem = "";
                        }
                        break;
                }
            }
            //统计并输出
            int res = 0;
            while(!s1.isEmpty()) {
                res += s1.pop();
            }
            System.out.println(res);
        }
    }
    public static boolean nextIsNotNum(String str, int n, int len) {
        int temp = -1;
        try {
            temp = Integer.parseInt(String.valueOf(str.charAt(n+1)));
        } catch(Exception e) {
            temp = -1;
        }
        return temp != -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();
    }
}