华为OD机试 - 提取字符串中的最长合法简单数学表达式（Java & JS & Python & C）

题目描述

���取字符串中的最长合法简单数学表达式，字符串长度最长的，并计算表达式的值。如果没有，则返回 0 。

简单数学表达式只能包含以下内容：

• 0-9数字，符号+-*

  说明：

  1. 所有数字，计算结果都不超过long
  2. 如果有多个长度一样的，请返回第一个表达式的结果
  3. 数学表达式，必须是最长的，合法的
  4. 操作符不能连续出现，如 +--+1 是不合法的

  输入描述

  字符串

  输出描述

  表达式值

  用例

  输入	1-2abcd
  输出	-1
  说明	最长合法简单数学表达式是"1-2"，结果是-1

  题目解析

  注意！！！本题原题描述中没有 / 除号

  因此，本题的合法表达式不需要考虑 '/' 号，也就不用考虑除0，以及除法是整除还是小数除的问题。

  另外，本题的 +、-号仅作为运算符号，不作为正负号。因此 "+1"，"-1" 这种不能理解为合法的表达式。

  ---

  本题可以分为两步求解：

  1. 找出输入串中最长合法的表达式
  2. 计算最长合法表达式的结果

  ---

  关于1的求解，有两种思路：

  • 双指针
  • 正则匹配

    其中正则匹配实现起来比较简单，用于匹配合法表达式的正则也不是很难写，对应正则解析如下：

    对于python而言，为了更好地适配findall方法，我们可以对上面正则表达式中内层括号使用到非捕获组

    ---

    关于2的求解

    对于JS和Python而言，可以使用内置的eval函数计算字符串表达式的结果。

    更常规的思路是利用栈结构：

    找出最长合法表达式子串后，比如 "1-2*3+10+2"，我们需要注意表达式运算符优先级问题，即先乘，后加减，相同优先级的运算从左到右进行。

    这里我的思路是将 合法表达式串 进行分块，比如上面表达式可以分为：

    • 1
    • -2*3
    • 10
    • 2

      我们可以发现：

      • +、-运算符前面的操作数都是独立成块，比如上面表达式的操作数1，10
      • * 运算符前面的操作数则需要组合成块，比如上面表达式的操作数2后面是 * 运算符，因此 2 需要和 3 进行组合。

        分块之后，我们只需要求各块结果之和即可。

        具体逻辑实现如下：

        • 首先定义一个栈stack，用于保存各个块的结果；
        • 其次定义一个块的值容器numStr，用于临时缓存分块的值；
        • 最后定义一个块的系数变量numCoef，用于临时缓存分块的系数；

          扫描合法表达式串，如果当前扫描的字符c是：

          • c 是数字，则直接缓存进块的值容器numStr中
          • c 是 + 号，则打断前一个操作数的收集，此时我们应该将前一个操作数计算结果后加入到stack中，操作数 = int(numStr) * numCoef，同时更新numCoef = 1，因为c是+号，所以后一个操作数的系数为1
          • c 是 - 号，则打断前一个操作数的收集，此时我们应该将前一个操作数计算结果后加入到stack中，操作数 = int(numStr) * numCoef，同时更新numCoef = -1，因为c是-号，所以后一个操作数的系数为-1
          • c 是 * 号，则打断前一个操作数的收集，并且 * 前后的两个操作数需要组合，而 * 前面的操作数记录在stack栈顶中，我们可以取出stack栈顶值 记录到 numCoef 中，即 * 前面的操作数，可以当初 * 后面操作数的系数

            这块实现的更详细解析，可以参考：

            华为OD机试 - 符号运算（Java & JS & Python & C）_java 华为od机试,符号运算-CSDN博客

            ---

            2024.01.29

            本题按照上面解法，有考友反馈只能拿15%通过率，实在想不通是哪里还有问题，感觉上面思路已经很完美了。

            想了一个晚上，唯一可能的就是合法表达式的判断，本题没有直接说明合法表达式的限制规则，只是说：

            • 简单数学表达式只能包含：0-9数字，符号+-*
            • 操作符不能连续出现，如 +--+1 是不合法的

              其他的限制就没有了。

              按照上面解法的正则匹配

              如果输入串是："+1+2m2222"

              则该正则会依次匹配出合法表达式"1+2" 和 ”2222“，由于2222的长度更长，因此最长合法表达式是"2222"，计算结果也是2222。

              但是，我们根据题目对合法表达式的限制规则来看，其实："+1+2" 也是符合要求的：

              • 该表达式中只能包含：0-9数字，符号+-*
              • 该表达式中没有出现连续操作符

                那要是这样说的话，如果输入串是："+1+2+m22222"

                那么 "+1+2+" 是不是也算符合题目要求的合法表达式呢。。。。。

                我滴个乖，这个出题真是太不严谨了。。。。

                我更新了下面解法，让其可以完成 "+1+2" 的合法表达式识别，但是我不认为  "+1+2+" 是合法表达式，所以没有适配。

                网上搜了一圈，找到一个100%的python解法，但是感觉不对，有需要的可以找我要。

                JS算法源码

                正则+栈解法

                const rl = require("readline").createInterface({ input: process.stdin });var iter = rl[Symbol.asyncIterator]();const readline = async () => (await iter.next()).value;void (async function () {  const s = await readline();  console.log(getResult(s));})();function getResult(s) {  const maxLenExp = getMaxLenExp(s);  if (maxLenExp.length == 0) {    return 0;  } else {    return calcExpStr(maxLenExp);  }}function getMaxLenExp(s) {  // 下面正则无法匹配这样的数字串：+1+2  // const reg = /((\d+[+*-])*\d+)/g;  // 下面正则可以匹配到这样的数字串：+1+2  const reg = /([+-]?(\d+[+*-])*\d+)/g;  let maxLenExp = "";  let res;  while ((res = reg.exec(s)) != null) {    const exp = res[0];    if (exp.length > maxLenExp.length) {      maxLenExp = exp;    }  }  return maxLenExp;}function calcExpStr(exp) {  // 这里在表达式结尾追加"+0"是为了避免后面收尾操作，不理解的话，可以去掉此步，测试下"1-2"  exp += "+0";  // 记录表达式中各块的操作数  const stack = [];  // 各块操作数的"值"部分的缓存容器  let numStr = [];  // 各块操作数的"系数"部分，默认为1  let num_coef = 1;  // 如果合法的表达式可以+或-开头  const start = exp[0];  if (start == "+" || start == "-") {    // 将exp开头的符号去掉    exp = exp.slice(1);  }  if (start == "-") {    // 如果表达式开头是负号，则开头操作数的系数为-1    num_coef = -1;  }  // 处理剩余表达式  for (let c of exp) {    if (c >= "0" && c  (await iter.next()).value;void (async function () {  const s = await readline();  console.log(getResult(s));})();function getResult(s) {  const maxLenExp = getMaxLenExp(s);  if (maxLenExp.length == 0) {    return 0;  } else {    return eval(maxLenExp);  }}function getMaxLenExp(s) {  // 下面正则无法匹配这样的数字串：+1+2  // const reg = /((\d+[+*-])*\d+)/g;  // 下面正则可以匹配到这样的数字串：+1+2  const reg = /([+-]?(\d+[+*-])*\d+)/g;  let maxLenExp = "";  let res;  while ((res = reg.exec(s)) != null) {    const exp = res[0];    if (exp.length > maxLenExp.length) {      maxLenExp = exp;    }  }  return maxLenExp;}

                Java算法源码

                正则+栈解法

                import java.util.LinkedList;import java.util.Scanner;import java.util.regex.Matcher;import java.util.regex.Pattern;public class Main {  public static void main(String[] args) {    Scanner sc = new Scanner(System.in);    System.out.println(getResult(sc.nextLine()));  }  public static long getResult(String s) {    String maxLenExp = getMaxLenExp(s);    if (maxLenExp.length() == 0) {      return 0;    } else {      return calcExpStr(maxLenExp);    }  }  public static String getMaxLenExp(String s) {    // 下面正则无法匹配这样的数字串：+1+2    //    Matcher matcher = Pattern.compile("((\d+[+*-])*\d+)").matcher(s);    // 下面正则可以匹配到这样的数字串：+1+2    Matcher matcher = Pattern.compile("([+-]?(\d+[+*-])*\d+)").matcher(s);    String maxLenExp = "";    while (matcher.find()) {      String exp = matcher.group(0);      if (exp.length() > maxLenExp.length()) {        maxLenExp = exp;      }    }    return maxLenExp;  }  public static long calcExpStr(String exp) {    // 这里在表达式结尾追加"+0"是为了避免后面收尾操作，不理解的话，可以去掉此步，测试下"1-2"    exp += "+0";    // 记录表达式中各块的操作数    LinkedList stack = new LinkedList();    // 各块操作数的"值"部分的缓存容器    StringBuilder numStr = new StringBuilder();    // 各块操作数的"系数"部分，开头的操作数系数默认为1    long num_coef = 1;    // 如果合法的表达式可以+或-开头    char start = exp.charAt(0);    if (start == '+' || start == '-') {      // 将exp开头的符号去掉      exp = exp.substring(1);    }    if (start == '-') {      // 如果表达式开头是负号，则开头操作数的系数为-1      num_coef = -1;    }    // 处理剩余表达式    for (int i = 0; i = '0' && c = c >= '0':            numStr.append(c)            continue        # 如果扫描到的字符c是运算符，那么该运算符打断了前面操作数的扫描，前面操作数 = 系数 * 值        num = num_coef * int("".join(numStr))        stack.append(num)        # 清空缓存容器，用于下一个操作数的”值“记录        numStr.clear()        if c == '+':            # 如果运算符是加法，则后一个操作数的系数为1            num_coef = 1        elif c == '-':            # 如果运算符是减法，则后一个操作数的系数为-1            num_coef = -1        elif c == '*':            # 如果运算符是乘法，则后一个操作数的系数为栈顶值，比如2*3，其中2可以当作3的系数            num_coef = stack.pop()    # 表达式分块后，每一块独立计算，所有块的和就是表达式的结果    return sum(stack)# 获取最长合法表达式def getMaxLenExp():    # 下面正则无法匹配这样的数字串：+1+2    # lst = re.compile(r"((?:\d+[+*-])*\d+)").findall(s)    # 下面正则可以匹配到这样的数字串：+1+2    lst = re.compile(r"([+-]?(?:\d+[+*-])*\d+)").findall(s)    maxLenExp = ""    for exp in lst:        if len(exp) > len(maxLenExp):            maxLenExp = exp    return maxLenExp# 算法入口def getResult():    maxLenExp = getMaxLenExp()    if len(maxLenExp) == 0:        return 0    else:        return calcExpStr(maxLenExp)# 算法调用print(getResult())

                正则+eval解法

                # 输入获取import res = input()# 获取最长合法表达式def getMaxLenExp():    # 下面正则无法匹配这样的数字串：+1+2    # lst = re.compile(r"((?:\d+[+*-])*\d+)").findall(s)    # 下面正则可以匹配到这样的数字串：+1+2    lst = re.compile(r"([+-]?(?:\d+[+*-])*\d+)").findall(s)    maxLenExp = ""    for exp in lst:        if len(exp) > len(maxLenExp):            maxLenExp = exp    return maxLenExp# 算法入口def getResult():    maxLenExp = getMaxLenExp()    if len(maxLenExp) == 0:        return 0    else:        return eval(maxLenExp)# 算法调用print(getResult())

                C算法源码

                双指针+栈解法

                #include #include #include #define MAX_SIZE 10000#define OPERATOR_NUM_LEN 100#define OPERATOR_NUM_SIZE 1000char s[MAX_SIZE] = {''};long calcExpStr(const char *exp) {    // 记录表达式中各块的操作数    long stack[OPERATOR_NUM_SIZE];    int stack_size = 0;    // 各块操作数的"值"部分的缓存容器    char numStr[OPERATOR_NUM_LEN] = {''};    int numStr_size = 0;    // 各块操作数的"系数"部分，默认为1    long num_coef = 1;    // 如果合法的表达式可以+或-开头    char start = exp[0];    if(start == '+' || start == '-') {        // 将exp开头的符号去掉        exp += 1;    }    if(start == '-') {        // 如果表达式开头是负号，则开头操作数的系数为-1        num_coef = -1;    }    int i = 0;    while (exp[i] != '') {        char c = exp[i];        if (c >= '0' && c  0) {        long num = num_coef * atol(numStr);        stack[stack_size++] = num;    }    // 表达式分块后，每一块独立计算，所有块的和就是表达式的结果    long res = 0;    for (int j = 0; j = '0' && c = 1 && (s[l - 1] == '+' || s[l - 1] == '-')) {            l--;            len++;        }        // 记录最长的合法表达式长度，以及起始位置        if (len > maxLen) {            maxLen = len;            start = l;        }        // 找到一个合法表达式后，继续找下一个合法表达式        l = r + 1;    }    if (start == -1) {        // 如果没找到合法表达式，则直接打印0        puts("0");    } else {        // 找到最长合法表达式，则计算其结果打印        s[start + maxLen] = '';        printf("%ld\n", calcExpStr(s + start));    }    return 0;}