字节跳动青训营——入营考核解答（持续更新中~~~）

考核内容：

在指定的题库中自主选择不少于 15 道算法题并完成解题，其中题目难度分配如下：

简单题不少于 10 道
中等题不少于 4 道
困难题不少于 1 道

解答代码

5.简单四则运算（中）

代码实现：

import java.util.Stack;

public class Main {
    public static int solution(String expression) {
        Stack<Integer> numStack = new Stack<>();
        Stack<Character> opStack = new Stack<>();

        // 遍历表达式
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);

            // 如果是数字，将其转换为整数并压入数字栈
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
                    num = num * 10 + (expression.charAt(i) - '0');
                    i++;
                }
                i--;
                numStack.push(num);
            }
            // 如果是左括号，直接压入运算符栈
            else if (c == '(') {
                opStack.push(c);
            }
            // 如果是右括号，进行计算直到遇到左括号
            else if (c == ')') {
                while (opStack.peek() != '(') {
                    char op = opStack.pop();
                    int num2 = numStack.pop();
                    int num1 = numStack.pop();

                    if (op == '+') {
                        numStack.push(num1 + num2);
                    } else if (op == '-') {
                        numStack.push(num1 - num2);
                    } else if (op == '*') {
                        numStack.push(num1 * num2);
                    } else if (op == '/') {
                        numStack.push(num1 / num2);
                    }
                }
                opStack.pop();
            }
            // 如果是运算符，根据优先级进行处理
            else if (isOperator(c)) {
                while (!opStack.isEmpty() && precedence(c) <= precedence(opStack.peek())) {
                    char op = opStack.pop();
                    int num2 = numStack.pop();
                    int num1 = numStack.pop();

                    if (op == '+') {
                        numStack.push(num1 + num2);
                    } else if (op == '-') {
                        numStack.push(num1 - num2);
                    } else if (op == '*') {
                        numStack.push(num1 * num2);
                    } else if (op == '/') {
                        numStack.push(num1 / num2);
                    }
                }
                opStack.push(c);
            }
        }

        // 处理剩余的运算符
        while (!opStack.isEmpty()) {
            char op = opStack.pop();
            int num2 = numStack.pop();
            int num1 = numStack.pop();

            if (op == '+') {
                numStack.push(num1 + num2);
            } else if (op == '-') {
                numStack.push(num1 - num2);
            } else if (op == '*') {
                numStack.push(num1 * num2);
            } else if (op == '/') {
                numStack.push(num1 / num2);
            }
        }

        // 返回数字栈的栈顶元素即为结果
        return numStack.pop();
    }

    // 判断是否为运算符
    public static boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }

    // 定义运算符的优先级
    public static int precedence(char op) {
        if (op == '+' || op == '-') {
            return 1;
        } else if (op == '*' || op == '/') {
            return 2;
        }
        return -1;
    }

    public static void main(String[] args) {
        // You can add more test cases here
        System.out.println(solution("1+1") == 2);
        System.out.println(solution("3+4*5/(3+2)") == 7);
        System.out.println(solution("4+2*5-2/1") == 12);
        System.out.println(solution("(1+(4+5+2)-3)+(6+8)") == 23);
    }
}