华为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 <= "9") {
      numStr.push(c);
      continue;
    }

    // 如果扫描到的字符c是运算符，那么该运算符打断了前面操作数的扫描，前面操作数 = 系数 * 值
    const num = num_coef * parseInt(numStr.join(""));
    stack.push(num);

    // 清空缓存容器，用于下一个操作数的”值“记录
    numStr = [];

    switch (c) {
      case "+":
        // 如果运算符是加法，则后一个操作数的系数为1
        num_coef = 1;
        break;
      case "-":
        // 如果运算符是减法，则后一个操作数的系数为-1
        num_coef = -1;
        break;
      case "*":
        // 如果运算符是乘法，则后一个操作数的系数为栈顶值，比如2*3，其中2可以当作3的系数
        num_coef = stack.pop();
        break;
    }
  }

  // 表达式分块后，每一块独立计算，所有块的和就是表达式的结果
  let res = 0;
  for (let num of stack) {
    res += num;
  }

  return res;
}

正则+eval解法

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 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<Long> 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 < exp.length(); i++) {
      char c = exp.charAt(i);

      if (c >= '0' && c <= '9') {
        numStr.append(c);
        continue;
      }

      // 如果扫描到的字符c是运算符，那么该运算符打断了前面操作数的扫描，前面操作数 = 系数 * 值
      long num = num_coef * Long.parseLong(numStr.toString());
      stack.add(num);

      // 清空缓存容器，用于下一个操作数的”值“记录
      numStr = new StringBuilder();

      switch (c) {
        case '+':
          // 如果运算符是加法，则后一个操作数的系数为1
          num_coef = 1;
          break;
        case '-':
          // 如果运算符是减法，则后一个操作数的系数为-1
          num_coef = -1;
          break;
        case '*':
          // 如果运算符是乘法，则后一个操作数的系数为栈顶值，比如2*3，其中2可以当作3的系数
          num_coef = stack.removeLast();
          break;
      }
    }

    // 表达式分块后，每一块独立计算，所有块的和就是表达式的结果
    long res = 0;
    for (long num : stack) {
      res += num;
    }

    return res;
  }
}

Python算法源码

正则+栈解法

# 输入获取
import re

s = input()


# 计算合法表达式的结果
def calcExpStr(exp):
    # 这里在表达式结尾追加"+0"是为了避免后面收尾操作，不理解的话，可以去掉此步，测试下"1-2"
    exp += '+0'

    # 记录表达式中各块的操作数
    stack = []
    # 各块操作数的"值"部分的缓存容器
    numStr = []

    # 各块操作数的"系数"部分，默认为1
    num_coef = 1

    # 如果合法的表达式可以+或-开头
    start = exp[0]
    if start == '+' or start == '-':
        # 将exp开头的符号去掉
        exp = exp[1:]

    if start == '-':
        # 如果表达式开头是负号，则开头操作数的系数为-1
        num_coef = -1

    # 处理剩余表达式
    for c in exp:
        if '9' >= 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 re

s = 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 <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_SIZE 10000
#define OPERATOR_NUM_LEN 100
#define OPERATOR_NUM_SIZE 1000

char s[MAX_SIZE] = {'\0'};

long calcExpStr(const char *exp) {
    // 记录表达式中各块的操作数
    long stack[OPERATOR_NUM_SIZE];
    int stack_size = 0;

    // 各块操作数的"值"部分的缓存容器
    char numStr[OPERATOR_NUM_LEN] = {'\0'};
    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] != '\0') {
        char c = exp[i];

        if (c >= '0' && c <= '9') {
            numStr[numStr_size++] = c;
        } else {
            // 如果扫描到的字符c是运算符，那么该运算符打断了前面操作数的扫描，前面操作数 = 系数 * 值
            long num = num_coef * atol(numStr);
            stack[stack_size++] = num;

            // 清空缓存容器，用于下一个操作数的”值“记录
            numStr_size = 0;
            memset(numStr, '\0', OPERATOR_NUM_LEN);

            if (c == '+') {
                // 如果运算符是加法，则后一个操作数的系数为1
                num_coef = 1;
            } else if (c == '-') {
                // 如果运算符是减法，则后一个操作数的系数为-1
                num_coef = -1;
            } else if (c == '*') {
                // 如果运算符是乘法，则后一个操作数的系数为栈顶值，比如2*3，其中2可以当作3的系数
                num_coef = stack[--stack_size];
            }
        }

        i++;
    }

    // 收尾处理
    if (numStr_size > 0) {
        long num = num_coef * atol(numStr);
        stack[stack_size++] = num;
    }

    // 表达式分块后，每一块独立计算，所有块的和就是表达式的结果
    long res = 0;
    for (int j = 0; j < stack_size; j++) {
        res += stack[j];
    }

    return res;
}

int isDigit(char c) {
    return c >= '0' && c <= '9';
}

int isOperator(char c) {
    return c == '+' || c == '-' || c == '*';
}

int main() {
    gets(s);

    // 记录最长合法表达式的长度
    int maxLen = 0;
    // 记录最长合法表达式的起始位置
    int start = -1;

    // 双指针找最长合法表达式
    int l = 0;
    int r = 0;

    while (s[r] != '\0') {
        // 合法表达式必须以数字开头
        // 如果+-开头的表达式也是合法的表达式，则需要添加当前代码135~138行逻辑
        while (s[l] != '\0' && !isDigit(s[l])) {
            l++;
        }

        if (s[l] == '\0') {
            break;
        }

        // l找到合法表达式的开头后，r指针扫开始描合法表达式剩余部门
        r = l + 1;

        while (s[r] != '\0') {
            // 如果r指针扫描到的是数字字符，则继续扫描
            // 如果r指针扫描到的是+-*符号，则需要看r-1字符是不是+-*符号，如果不是则继续扫描
            if (isDigit(s[r]) || (isOperator(s[r]) && !isOperator(s[r - 1]))) {
                r++;
            } else {
                // 其他情况中断r扫描
                break;
            }
        }

        // 此时 [l, r) 左闭右开范围就是合法表达式
        int len = r - l;

        // 注意如果r-1位置是+-*符号，则不能包含
        if (isOperator(s[r - 1])) {
            len -= 1;
        }

        // 如果认为 +1+2，-2*3 这种也是合法的表达式，则需要加入下面逻辑
        if (l >= 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] = '\0';
        printf("%ld\n", calcExpStr(s + start));
    }

    return 0;
}