题解 | #四则运算#

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
import java.util.Stack;

/**
 * @author zjx
 * @Date 2024-02-22 23:04:05
 * @Desc：四则运算
 * 【描述】
 * 输入一个表达式（用字符串表示），求这个表达式的值。
 * 保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,
 * ‘{’ ,‘}’。且表达式一定合法。
 * 数据范围：表达式计算结果和过程中满足 ∣val∣≤1000  ，字符串长度满足 1≤n≤1000
 * 【输入描述】：
 * 输入一个算术表达式
 * 【输出描述】：
 * 得到计算结果
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        //将其他括号，替换成小括号
        s = s.replace("{", "(");
        s = s.replace("[", "(");
        s = s.replace("}", ")");
        s = s.replace("]", ")");

        System.out.println(withParenthesis(s));

    }

    /**
     * 核心思想，想有括号的表达式，转换成没有括号的
     * @param str
     * @return
     */
    public static int withParenthesis(String str) {
        Deque<Character> deque = new ArrayDeque<>();
        int index = 0;
        while (index < str.length()) {
            char cur = str.charAt(index);
            if (cur != ')') {
                //不是）就直接添加
                deque.add(cur);
            } else {
                //如果是），那么就博纳之前的数据弹出，并计算，然后加入栈
                //这样就是达到取出（）的效果
                //例如：1+（1+2+3）--> 这样s = 1+2+3
                //式子就会变成 1+6，达到去除（）的效果
                StringBuilder s = new StringBuilder();
                while (!deque.isEmpty() && deque.getLast() != '(') {
                    s.insert(0, deque.pollLast());
                }
                if (deque.getLast() == '(') {
                    deque.pollLast();
                }
                char[] charArray = String.valueOf(withoutParenthesis(
                                                      s.toString())).toCharArray();
                for (char c : charArray) {
                    deque.add(c);
                }
            }
            index++;
        }

        StringBuilder s = new StringBuilder();
        for (Character character : deque) {
            s.append(character);
        }

        return withoutParenthesis(s.toString());
    }


    /**
     * 没有括号的四则运算
     * 可以把所有的加减号，看做判定一个数的正负，然后将所有的数加起来，就是结果
     * 具体步骤如下：
     * 1.flag用于判定正负，+号时不动。-号时取反
     * 2.遇到数字的时候，将数字添加进nums，然后添加“+”，但是如果之前是（乘除号）的时候
     *   就不添加加号，此时要进行计算
     * 3.遇到乘除号直接添加，并且在遇到下一个数字的时候，要弹出两个数进行计算，然后将结果
     *   添加进nums
     * 4.全部遍历结束，所有的数加起来，就是答案
     */
    public static int withoutParenthesis(String str) {
        Deque<Integer> nums = new ArrayDeque<>();
        Deque<Character> operate = new ArrayDeque<>();
        int index = 0;
        int flag = 1;
        //碰到*/就设为true，在加入下一个数字的时候，要进行计算了
        boolean cal = false;
        while (index < str.length()) {
            char cur = str.charAt(index);
            //遇到数字就进行添加，添加的时候注意正负数
            if (Character.isDigit(cur)) {
                if (!nums.isEmpty() && !cal) {
                    operate.add('+');
                }

                int n = cur - '0';
                //如果下一个还是数字
                while (index + 1 < str.length() && Character.isDigit(str.charAt(index + 1))) {
                    n = 10 * n + (str.charAt(index + 1) - '0');
                    index++;
                }

                if (flag == 1) {
                    nums.add(flag * n);
                } else {
                    nums.add(flag * n);
                }
                //添加完数字，还原flag
                flag = 1;

                //添加完数字，看是否需要计算
                if (cal) {
                    int next = nums.pollLast();
                    int pre = nums.pollLast();
                    char o = operate.pollLast();
                    if (o == '*') {
                        nums.add(pre * next);
                    } else {
                        nums.add(pre / next);
                    }
                    cal = false;
                }
            }

            //碰到‘-’,就
            if (cur == '-') {
                flag = flag * (-1);
            }

            if (cur == '*' || cur == '/') {
                operate.add(cur);
                cal = true;
            }

            index++;
        }

        int res = 0;

        for (Integer num : nums) {
            res += num;
        }

        return res;
    }
}