牛客-四则运算解法

发表于： 更新于： 分类于：
字数： 491 阅读：≈ 3分钟 浏览： 评论：

描述

牛客网题目: 四则运算 输入一个表达式（用字符串表示）, 求这个表达式的值. 保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’. 且表达式一定合法.

数据范围：表达式计算结果和过程中满足∣val∣≤1000 ，字符串长度满足 1≤n≤1000

输入描述：

输入一个算术表达式

输出描述：

得到计算结果

思路

使用栈分别存储数字和操作符, 通过出入栈来完成表达式计算.

步骤

  1. 遍历字符串表达式;
  2. 如果为左括号 (包括大括号, 中括号和小括号), 需要从当前位置遍历找到括号结尾位置, 使用递归方式计算括号中的表达式;
  3. 如果为数字则入数字栈, 需要考虑负数和多位数字的情况;
  4. 如果为四则远算符号, 分两种情况:
    • 如果符号栈为空栈, 则直接入栈;
    • 如果符号栈不为空, 当前的符号优先级高于栈顶符号, 则直接入栈; 如果当前符号优先级小于或者等于栈顶符号, 从数栈中pop出两个数, 再从符号栈中pop出一个符号, 进行运算, 将结果入数栈, 然后操作符入符号栈;
  5. 当表达式扫描完, 顺序的从数栈和符号栈中pop出相应的数和符号, 并运算;
  6. 最后数栈中只有一个数字及为表达式的结果.

代码实现 

/**
 * @Description: Calculator
 * @Author : [email protected]
 * @Create Date: 2023-05-18
 */
public class Calculator {
public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String exp = in.nextLine();
            BigDecimal res = solution(exp);
            System.out.println(res);
        }
    }

    public static BigDecimal solution(String exp) {
        Stack<BigDecimal> numStack = new Stack<>();
        Stack<Character> opStack = new Stack<>();
        BigDecimal num1 = BigDecimal.ZERO, num2 = BigDecimal.ZERO;
        for (int i = 0; i < exp.length(); i++) {
            char ch = exp.charAt(i);
            // 左括号
            if (ch == '(' || ch == '[' || ch == '{') {
                opStack.push(ch);
                int end = i;
                // 找到括号结尾位置
                for (int j = i + 1; j < exp.length(); j++) {
                    char k = exp.charAt(j);
                    if (k == '(' || k == '[' || k == '{') {
                        opStack.push(k);
                    } else if (k == ')' || k == ']' || k == '}') {
                        opStack.pop();
                        if (opStack.isEmpty() ||
                                (opStack.peek() != '(' && opStack.peek() != '[' && opStack.peek() != '{')
                        ) {
                            end = j;
                            break;
                        }
                    }
                }
                // 递归计算括号中的结果
                BigDecimal solution = solution(exp.substring(i + 1, end));
                numStack.push(solution);
                // 更新 i 值
                i = end;
            } else if ((i == 0 && ch == '-') || (Character.isDigit(ch))) { // 数字, 需要考虑负数和多位数字场景
                String num = ch + "";
                i ++;
                while (i < exp.length() && Character.isDigit(exp.charAt(i))) {
                    num += exp.charAt(i);
                    i++;
                }
                numStack.push(new BigDecimal(num));
                i--;
            } else { // 操作符号 +-*/
                if (!opStack.isEmpty()) {
                    // 当前符号优先级小于或者等于栈顶符号, 从数栈中pop出两个数, 再从符号栈中pop出一个符号, 进行运算, 将结果入数栈
                    if (ch == '+' || ch == '-') {
                        // +- 需要将栈中的全部计算
                        while (!opStack.isEmpty()) {
                            num1 = numStack.pop();
                            num2 = numStack.pop();
                            char op = opStack.pop();
                            BigDecimal res = calc(num1, num2, op);
                            numStack.push(res);
                        }
                    } else if ((ch == '*' || ch == '/')
                            && (opStack.peek() == '*' || opStack.peek() == '/')
                    ) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        char op = opStack.pop();
                        BigDecimal res = calc(num1, num2, op);
                        numStack.push(res);
                    }
                }
                // 操作符栈为空或者当前的符号优先级高于栈顶符号, 则直接入栈
                opStack.push(ch);
            }
        }
        // 计算剩余元素结果
        while (!opStack.empty()) {
            num1 = numStack.pop();
            num2 = numStack.pop();
            char op = opStack.pop();
            BigDecimal res = calc(num1, num2, op);
            numStack.push(res);
        }
        return numStack.pop();
    }

    public static BigDecimal calc(BigDecimal num1, BigDecimal num2, char op) {
        BigDecimal res = BigDecimal.ZERO;
        switch (op) {
            case '+':
                res = num1.add(num2);
                break;
            case '-':
                res = num2.subtract(num1); // 顺序
                break;
            case '*':
                res = num1.multiply(num2);
                break;
            case '/': // 精度保留8位小数
                if (num1.compareTo(BigDecimal.ZERO) != 0) {
                    res = num2.divide(num1, 8, BigDecimal.ROUND_HALF_UP);
                }
                break;
            default:
                break;
        }
        return res;
    }
}

其他解法

  • 使用Java 8的Nashorn JavaScript引擎
  • 代码
    @Test
    public void scriptEngine() throws ScriptException {
        String exp = "3+2*{1+2*[-4/(8-5)+7]}";
        exp = exp.replace("{", "(")
                .replace("}", ")")
                .replace("[", "(")
                .replace("]", ")");
        ScriptEngineManager scriptEngineManager = new ScriptEngineManager();
        ScriptEngine engine = scriptEngineManager.getEngineByName("nashorn");
        System.out.println(engine.eval(exp));
    }