Java: 对字符串计算公式实现加减乘除运算

原创

Janesong

修改于 2024-08-27 09:04:53

3810

修改于 2024-08-27 09:04:53

文章被收录于专栏：Java编程

最近看到一段面试编码视频：字符串计算加减乘除，发现网上很多是【从左到右遍历，两两计算】，没有考虑优先级事项，一直手痒，周末在家倒弄一下。

题目及说明

题目：给一段字符串计算公式，实现加减乘除运算

eg: 输入：“5*45000+246/123”，输出：225002

输入：“1+2-3”，输出：0

输入：“2-10*1/5”，输出：0

前提：只有正整数参与计算，么有括号，且录入公式一定是可以计算的。

code思路

原则：在整个遍历字符串过程中做存入计算数组toSum 动作，而这个动作穿插着计算高优先级(乘除操作)。

1、从左到右遍历整个字符串，将字符串拆分成计算数组expressionAarray； // 主要是将多位连续数字存放到一个index位，作为一个参与计算的数值

2、对计算数组expressionAarray，从左到右开始计算乘除操作，存放到toSum数组。一遍结束后，必然只剩下加减；

3、对toSum数组进行计算，返回最终结果。

优势：简单，易理解。复杂度也就是O(n)级别

弊端：

补充：

本小代码没有考虑数据溢出，也没有考虑字符串公式合法性，只是想抛砖迎玉，侧重计算优先级。对于数值较大的需要借助BigDecimal或BigInt
代码么有使用Stack，是因为在实际coding中发现：单向栈，只支持【先进后出】，对计算同等优先级有误。比如：对于【10-2+3】从左到右入栈后，栈顶元素为3，出栈时，先计算（2+3) ==》得到5，然后才计算【10-5】，显然与正确答案 11 不符合。
对于公式中有括号的，就需要【中缀表达式转化为后缀表达式(后缀表达式也叫逆波兰表达式法)】，可以参考：https://www.jb51.net/jiaoben/303140r7w.htm【文章指明需要Stack和Queue同时完成计算器的计算】

code展示

myCalculte

// 考虑计算优先级，不考虑括号
private static Integer myCalculate(String expressionString) {
    if (null == expressionString || expressionString.length() <= 0) return null;
    String[] expressionArray = getExpressionArray(expressionString);
    if (expressionArray.length == 1) return Integer.valueOf(expressionArray[0]);

    String[] toSum = new String[expressionArray.length];
    if(expressionString.contains("*") || expressionString.contains("/")) {
        toSum[0] = String.valueOf(expressionArray[0]);
        int a = 0, b = 0;
        int index = 1;    // 控制 toSum的下标
        for (int i = 1; i < expressionArray.length-1; i++) {
            if(expressionArray[i].equals("*")) {
                a = Integer.valueOf(expressionArray[i-1]);
                b = Integer.valueOf(expressionArray[i+1]);
                toSum[index-1] = String.valueOf(a * b);
                expressionArray[i+1] = toSum[index-1];
                i++;
            } else if (expressionArray[i].equals("/")) {
                a = Integer.valueOf(expressionArray[i-1]);
                b = Integer.valueOf(expressionArray[i+1]);
                toSum[index-1] = String.valueOf(a / b);
                expressionArray[i+1] = toSum[index-1];
                i++;
            } else {
                toSum[index] = expressionArray[i];
                index++;
            }
        }
        // 防止丢:最后的加减丢数字
        if (!(expressionArray[expressionArray.length-2].equals("/") || expressionArray[expressionArray.length-2].equals("*"))) {
            toSum[toSum.length - 1] = expressionArray[expressionArray.length - 1];
        }
    } else {
        // 么有*/就直接搬迁复制
        for (int i = 0; i < expressionArray.length; i++) {
            toSum[i] = expressionArray[i];
        }
    }

    String[] toSumShort = Utils.removeNullValues(toSum);
    int result = Integer.valueOf(toSumShort[0]);    // 第一个位置必然是 数字
    for (int i = 1; i < toSumShort.length-1; i+=2) {
        if (toSumShort[i].equals("+")) {
            result += Integer.valueOf(toSumShort[i+1]);
        } else {
            result -= Integer.valueOf(toSumShort[i+1]);
        }
    }

    return result;      // 返回最终结果
}

辅助方法：

// 字符串转计算数组
private static String[] getExpressionArray(String expression) {
    if (null == expression || expression.length() <= 0) return null;

    String[] format = new String[expression.length()];
    char[] tokenChars = expression.toCharArray();
    int index = 0;
    for (int i = 0; i < tokenChars.length; i++) {
        if (Character.isLetterOrDigit(tokenChars[i]) || tokenChars[i] == '.') {
            if (null == format[index]) {
                format[index] = String.valueOf(tokenChars[i]);
            } else {
                format[index] += String.valueOf(tokenChars[i]);
            }
        } else {
            index++;    // 与前面的数字分离
            format[index] = String.valueOf(tokenChars[i]);
            index++;    // 与后面的数字分离
        }
    }
    return Utils.removeNullValues(format);
}

// 去除字符串数组里空元素
public static String[] removeNullValues(String[] array) {
    List<String> list = new ArrayList<>();
    for (String element : array) {
        if (element != null) {
            list.add(element);
        }
    }
    return list.toArray(new String[0]);
}

第三方code

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;

// 使用第三方正确答案: 有优先级、小括号。补充：【5*45000+123/456】计算有问题
private static Integer func(String expression) {
    ScriptEngineManager manager = new ScriptEngineManager();
    ScriptEngine engine = manager.getEngineByName("js");

    try {
        Object result = engine.eval(expression);
        return Integer.valueOf(result.toString());
    } catch (ScriptException e) {
        e.printStackTrace();
    }

    return null;
}

验证

public static void main(String[] args) {
    System.out.println("func(1+2-3)        = " + func("1+2-3"));
    System.out.println("myCalculate(1+2-3) = " + myCalculate("1+2-3"));

    System.out.println("func(1+2*3)        = " + func("1+2*3"));
    System.out.println("myCalculate(1+2*3) = " + myCalculate("1+2*3"));

    System.out.println("func(1*2+3)        = " + func("1*2+3"));
    System.out.println("myCalculate(1*2+3) = " + myCalculate("1*2+3"));

    System.out.println("func(10-10/5+2)        = " + func("10-10/5+2"));
    System.out.println("myCalculate(10-10/5+2) = " + myCalculate("10-10/5+2"));

    System.out.println("func(2-10*1/5)        = " + func("2-10*1/5"));
    System.out.println("myCalculate(2-10*1/5) = " + myCalculate("2-10*1/5"));

    System.out.println("func(2-10/5*5/2)        = " + func("2-10/5*5/2"));
    System.out.println("myCalculate(2-10/5*5/2) = " + myCalculate("2-10/5*5/2"));

    // 多位数计算
    System.out.println("func(400/50-20)        = " + func("400/50-20"));
    System.out.println("myCalculate(400/50-20) = " + myCalculate("400/50-20"));

    System.out.println("func(400/50+2*5)        = " + func("400/50+2*5"));
    System.out.println("myCalculate(400/50+2*5) = " + myCalculate("400/50+2*5"));

    System.out.println("func(1000+200-3000)        = " + func("1000+200-3000"));
    System.out.println("myCalculate(1000+200-3000) = " + myCalculate("1000+200-3000"));

    System.out.println("func(10+20*1051)        = " + func("10+20*1051"));
    System.out.println("myCalculate(10+20*1051) = " + myCalculate("10+20*1051"));

    System.out.println("func(5*45000+246/123)        = " + func("5*45000+246/123"));
    System.out.println("myCalculate(5*45000+246/123) = " + myCalculate("5*45000+246/123"));
}