题目描述

提取字符串中的最长合法简单数学表达式,字符串长度最长的,并计算表达式的值。如果没有,则返回 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+2const reg = /([+-]" /> maxLenExp.length) {maxLenExp = exp;}}return maxLenExp;}function calcExpStr(exp) {// 这里在表达式结尾追加"+0"是为了避免后面收尾操作,不理解的话,可以去掉此步,测试下"1-2"exp += "+0";// 记录表达式中各块的操作数const stack = [];// 各块操作数的"值"部分的缓存容器let numStr = [];// 各块操作数的"系数"部分,默认为1let num_coef = 1;// 如果合法的表达式可以+或-开头const start = exp[0];if (start == "+" || start == "-") {// 将exp开头的符号去掉exp = exp.slice(1);}if (start == "-") {// 如果表达式开头是负号,则开头操作数的系数为-1num_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 "+":// 如果运算符是加法,则后一个操作数的系数为1num_coef = 1;break;case "-":// 如果运算符是减法,则后一个操作数的系数为-1num_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+2const 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+2Matcher 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();// 各块操作数的"系数"部分,开头的操作数系数默认为1long num_coef = 1;// 如果合法的表达式可以+或-开头char start = exp.charAt(0);if (start == '+' || start == '-') {// 将exp开头的符号去掉exp = exp.substring(1);}if (start == '-') {// 如果表达式开头是负号,则开头操作数的系数为-1num_coef = -1;}// 处理剩余表达式for (int i = 0; i = '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 '+':// 如果运算符是加法,则后一个操作数的系数为1num_coef = 1;break;case '-':// 如果运算符是减法,则后一个操作数的系数为-1num_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 res = input()# 计算合法表达式的结果def calcExpStr(exp):# 这里在表达式结尾追加"+0"是为了避免后面收尾操作,不理解的话,可以去掉此步,测试下"1-2"exp += '+0'# 记录表达式中各块的操作数stack = []# 各块操作数的"值"部分的缓存容器numStr = []# 各块操作数的"系数"部分,默认为1num_coef = 1# 如果合法的表达式可以+或-开头start = exp[0]if start == '+' or start == '-':# 将exp开头的符号去掉exp = exp[1:]if start == '-':# 如果表达式开头是负号,则开头操作数的系数为-1num_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 == '+':# 如果运算符是加法,则后一个操作数的系数为1num_coef = 1elif c == '-':# 如果运算符是减法,则后一个操作数的系数为-1num_coef = -1elif 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+2lst = re.compile(r"([+-]?(?:\d+[+*-])*\d+)").findall(s)maxLenExp = ""for exp in lst:if len(exp) > len(maxLenExp):maxLenExp = expreturn maxLenExp# 算法入口def getResult():maxLenExp = getMaxLenExp()if len(maxLenExp) == 0:return 0else:return calcExpStr(maxLenExp)# 算法调用print(getResult())
正则+eval解法
# 输入获取import res = input()# 获取最长合法表达式def getMaxLenExp():# 下面正则无法匹配这样的数字串:+1+2# lst = re.compile(r"((?:\d+[+*-])*\d+)").findall(s)# 下面正则可以匹配到这样的数字串:+1+2lst = re.compile(r"([+-]?(?:\d+[+*-])*\d+)").findall(s)maxLenExp = ""for exp in lst:if len(exp) > len(maxLenExp):maxLenExp = expreturn maxLenExp# 算法入口def getResult():maxLenExp = getMaxLenExp()if len(maxLenExp) == 0:return 0else: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] = {'\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;// 各块操作数的"系数"部分,默认为1long num_coef = 1;// 如果合法的表达式可以+或-开头char start = exp[0];if(start == '+' || start == '-') {// 将exp开头的符号去掉exp += 1;}if(start == '-') {// 如果表达式开头是负号,则开头操作数的系数为-1num_coef = -1;}int i = 0;while (exp[i] != '\0') {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) {// 如果没找到合法表达式,则直接打印0puts("0");} else {// 找到最长合法表达式,则计算其结果打印s[start + maxLen] = '\0';printf("%ld\n", calcExpStr(s + start));}return 0;}