devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：羊村懒王 | 2024-03-01 11:09:16

赞

踩

提取字符串中的最长数学表达式

题目描述

提取字符串中的最长合法简单数学表达式，字符串长度最长的，并计算表达式的值。如果没有，则返回 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算法源码

正则+栈解法
  1. const rl = require("readline").createInterface({ input: process.stdin });
  2. var iter = rl[Symbol.asyncIterator]();
  3. const readline = async () => (await iter.next()).value;
  4.  
  5. void (async function () {
  6.   const s = await readline();
  7.   console.log(getResult(s));
  8. })();
  9.  
  10. function getResult(s) {
  11.   const maxLenExp = getMaxLenExp(s);
  12.  
  13.   if (maxLenExp.length == 0) {
  14.     return 0;
  15.   } else {
  16.     return calcExpStr(maxLenExp);
  17.   }
  18. }
  19.  
  20. function getMaxLenExp(s) {
  21.   // 下面正则无法匹配这样的数字串：+1+2
  22.   // const reg = /((\d+[+*-])*\d+)/g;
  23.  
  24.   // 下面正则可以匹配到这样的数字串：+1+2
  25.   const reg = /([+-]?(\d+[+*-])*\d+)/g;
  26.  
  27.   let maxLenExp = "";
  28.  
  29.   let res;
  30.   while ((res = reg.exec(s)) != null) {
  31.     const exp = res[0];
  32.  
  33.     if (exp.length > maxLenExp.length) {
  34.       maxLenExp = exp;
  35.     }
  36.   }
  37.  
  38.   return maxLenExp;
  39. }
  40.  
  41. function calcExpStr(exp) {
  42.   // 这里在表达式结尾追加"+0"是为了避免后面收尾操作，不理解的话，可以去掉此步，测试下"1-2"
  43.   exp += "+0";
  44.  
  45.   // 记录表达式中各块的操作数
  46.   const stack = [];
  47.   // 各块操作数的"值"部分的缓存容器
  48.   let numStr = [];
  49.  
  50.   // 各块操作数的"系数"部分，默认为1
  51.   let num_coef = 1;
  52.  
  53.   // 如果合法的表达式可以+或-开头
  54.   const start = exp[0];
  55.   if (start == "+" || start == "-") {
  56.     // 将exp开头的符号去掉
  57.     exp = exp.slice(1);
  58.   }
  59.  
  60.   if (start == "-") {
  61.     // 如果表达式开头是负号，则开头操作数的系数为-1
  62.     num_coef = -1;
  63.   }
  64.  
  65.   // 处理剩余表达式
  66.   for (let c of exp) {
  67.     if (c >= "0" && c <= "9") {
  68.       numStr.push(c);
  69.       continue;
  70.     }
  71.  
  72.     // 如果扫描到的字符c是运算符，那么该运算符打断了前面操作数的扫描，前面操作数 = 系数 * 值
  73.     const num = num_coef * parseInt(numStr.join(""));
  74.     stack.push(num);
  75.  
  76.     // 清空缓存容器，用于下一个操作数的”值“记录
  77.     numStr = [];
  78.  
  79.     switch (c) {
  80.       case "+":
  81.         // 如果运算符是加法，则后一个操作数的系数为1
  82.         num_coef = 1;
  83.         break;
  84.       case "-":
  85.         // 如果运算符是减法，则后一个操作数的系数为-1
  86.         num_coef = -1;
  87.         break;
  88.       case "*":
  89.         // 如果运算符是乘法，则后一个操作数的系数为栈顶值，比如2*3，其中2可以当作3的系数
  90.         num_coef = stack.pop();
  91.         break;
  92.     }
  93.   }
  94.  
  95.   // 表达式分块后，每一块独立计算，所有块的和就是表达式的结果
  96.   let res = 0;
  97.   for (let num of stack) {
  98.     res += num;
  99.   }
  100.  
  101.   return res;
  102. }
正则+eval解法
  1. const rl = require("readline").createInterface({ input: process.stdin });
  2. var iter = rl[Symbol.asyncIterator]();
  3. const readline = async () => (await iter.next()).value;
  4.  
  5. void (async function () {
  6.   const s = await readline();
  7.   console.log(getResult(s));
  8. })();
  9.  
  10. function getResult(s) {
  11.   const maxLenExp = getMaxLenExp(s);
  12.  
  13.   if (maxLenExp.length == 0) {
  14.     return 0;
  15.   } else {
  16.     return eval(maxLenExp);
  17.   }
  18. }
  19.  
  20. function getMaxLenExp(s) {
  21.   // 下面正则无法匹配这样的数字串：+1+2
  22.   // const reg = /((\d+[+*-])*\d+)/g;
  23.  
  24.   // 下面正则可以匹配到这样的数字串：+1+2
  25.   const reg = /([+-]?(\d+[+*-])*\d+)/g;
  26.  
  27.   let maxLenExp = "";
  28.  
  29.   let res;
  30.   while ((res = reg.exec(s)) != null) {
  31.     const exp = res[0];
  32.  
  33.     if (exp.length > maxLenExp.length) {
  34.       maxLenExp = exp;
  35.     }
  36.   }
  37.  
  38.   return maxLenExp;
  39. }

Java算法源码

正则+栈解法
  1. import java.util.LinkedList;
  2. import java.util.Scanner;
  3. import java.util.regex.Matcher;
  4. import java.util.regex.Pattern;
  5.  
  6. public class Main {
  7.   public static void main(String[] args) {
  8.     Scanner sc = new Scanner(System.in);
  9.     System.out.println(getResult(sc.nextLine()));
  10.   }
  11.  
  12.   public static long getResult(String s) {
  13.     String maxLenExp = getMaxLenExp(s);
  14.  
  15.     if (maxLenExp.length() == 0) {
  16.       return 0;
  17.     } else {
  18.       return calcExpStr(maxLenExp);
  19.     }
  20.   }
  21.  
  22.   public static String getMaxLenExp(String s) {
  23.     // 下面正则无法匹配这样的数字串：+1+2
  24.     //    Matcher matcher = Pattern.compile("((\\d+[+*-])*\\d+)").matcher(s);
  25.  
  26.     // 下面正则可以匹配到这样的数字串：+1+2
  27.     Matcher matcher = Pattern.compile("([+-]?(\\d+[+*-])*\\d+)").matcher(s);
  28.  
  29.     String maxLenExp = "";
  30.  
  31.     while (matcher.find()) {
  32.       String exp = matcher.group(0);
  33.  
  34.       if (exp.length() > maxLenExp.length()) {
  35.         maxLenExp = exp;
  36.       }
  37.     }
  38.  
  39.     return maxLenExp;
  40.   }
  41.  
  42.   public static long calcExpStr(String exp) {
  43.     // 这里在表达式结尾追加"+0"是为了避免后面收尾操作，不理解的话，可以去掉此步，测试下"1-2"
  44.     exp += "+0";
  45.  
  46.     // 记录表达式中各块的操作数
  47.     LinkedList<Long> stack = new LinkedList<>();
  48.     // 各块操作数的"值"部分的缓存容器
  49.     StringBuilder numStr = new StringBuilder();
  50.  
  51.     // 各块操作数的"系数"部分，开头的操作数系数默认为1
  52.     long num_coef = 1;
  53.  
  54.     // 如果合法的表达式可以+或-开头
  55.     char start = exp.charAt(0);
  56.  
  57.     if (start == '+' || start == '-') {
  58.       // 将exp开头的符号去掉
  59.       exp = exp.substring(1);
  60.     }
  61.  
  62.     if (start == '-') {
  63.       // 如果表达式开头是负号，则开头操作数的系数为-1
  64.       num_coef = -1;
  65.     }
  66.  
  67.     // 处理剩余表达式
  68.     for (int i = 0; i < exp.length(); i++) {
  69.       char c = exp.charAt(i);
  70.  
  71.       if (c >= '0' && c <= '9') {
  72.         numStr.append(c);
  73.         continue;
  74.       }
  75.  
  76.       // 如果扫描到的字符c是运算符，那么该运算符打断了前面操作数的扫描，前面操作数 = 系数 * 值
  77.       long num = num_coef * Long.parseLong(numStr.toString());
  78.       stack.add(num);
  79.  
  80.       // 清空缓存容器，用于下一个操作数的”值“记录
  81.       numStr = new StringBuilder();
  82.  
  83.       switch (c) {
  84.         case '+':
  85.           // 如果运算符是加法，则后一个操作数的系数为1
  86.           num_coef = 1;
  87.           break;
  88.         case '-':
  89.           // 如果运算符是减法，则后一个操作数的系数为-1
  90.           num_coef = -1;
  91.           break;
  92.         case '*':
  93.           // 如果运算符是乘法，则后一个操作数的系数为栈顶值，比如2*3，其中2可以当作3的系数
  94.           num_coef = stack.removeLast();
  95.           break;
  96.       }
  97.     }
  98.  
  99.     // 表达式分块后，每一块独立计算，所有块的和就是表达式的结果
  100.     long res = 0;
  101.     for (long num : stack) {
  102.       res += num;
  103.     }
  104.  
  105.     return res;
  106.   }
  107. }

Python算法源码

正则+栈解法
  1. # 输入获取
  2. import re
  3.  
  4. s = input()
  5.  
  6.  
  7. # 计算合法表达式的结果
  8. def calcExpStr(exp):
  9.     # 这里在表达式结尾追加"+0"是为了避免后面收尾操作，不理解的话，可以去掉此步，测试下"1-2"
  10.     exp += '+0'
  11.  
  12.     # 记录表达式中各块的操作数
  13.     stack = []
  14.     # 各块操作数的"值"部分的缓存容器
  15.     numStr = []
  16.  
  17.     # 各块操作数的"系数"部分，默认为1
  18.     num_coef = 1
  19.  
  20.     # 如果合法的表达式可以+或-开头
  21.     start = exp[0]
  22.     if start == '+' or start == '-':
  23.         # 将exp开头的符号去掉
  24.         exp = exp[1:]
  25.  
  26.     if start == '-':
  27.         # 如果表达式开头是负号，则开头操作数的系数为-1
  28.         num_coef = -1
  29.  
  30.     # 处理剩余表达式
  31.     for c in exp:
  32.         if '9' >= c >= '0':
  33.             numStr.append(c)
  34.             continue
  35.  
  36.         # 如果扫描到的字符c是运算符，那么该运算符打断了前面操作数的扫描，前面操作数 = 系数 * 值
  37.         num = num_coef * int("".join(numStr))
  38.         stack.append(num)
  39.  
  40.         # 清空缓存容器，用于下一个操作数的”值“记录
  41.         numStr.clear()
  42.  
  43.         if c == '+':
  44.             # 如果运算符是加法，则后一个操作数的系数为1
  45.             num_coef = 1
  46.         elif c == '-':
  47.             # 如果运算符是减法，则后一个操作数的系数为-1
  48.             num_coef = -1
  49.         elif c == '*':
  50.             # 如果运算符是乘法，则后一个操作数的系数为栈顶值，比如2*3，其中2可以当作3的系数
  51.             num_coef = stack.pop()
  52.  
  53.     # 表达式分块后，每一块独立计算，所有块的和就是表达式的结果
  54.     return sum(stack)
  55.  
  56.  
  57. # 获取最长合法表达式
  58. def getMaxLenExp():
  59.     # 下面正则无法匹配这样的数字串：+1+2
  60.     # lst = re.compile(r"((?:\d+[+*-])*\d+)").findall(s)
  61.  
  62.     # 下面正则可以匹配到这样的数字串：+1+2
  63.     lst = re.compile(r"([+-]?(?:\d+[+*-])*\d+)").findall(s)
  64.  
  65.     maxLenExp = ""
  66.  
  67.     for exp in lst:
  68.         if len(exp) > len(maxLenExp):
  69.             maxLenExp = exp
  70.  
  71.     return maxLenExp
  72.  
  73.  
  74. # 算法入口
  75. def getResult():
  76.     maxLenExp = getMaxLenExp()
  77.  
  78.     if len(maxLenExp) == 0:
  79.         return 0
  80.     else:
  81.         return calcExpStr(maxLenExp)
  82.  
  83.  
  84. # 算法调用
  85. print(getResult())
正则+eval解法
  1. # 输入获取
  2. import re
  3.  
  4. s = input()
  5.  
  6.  
  7. # 获取最长合法表达式
  8. def getMaxLenExp():
  9.     # 下面正则无法匹配这样的数字串：+1+2
  10.     # lst = re.compile(r"((?:\d+[+*-])*\d+)").findall(s)
  11.  
  12.     # 下面正则可以匹配到这样的数字串：+1+2
  13.     lst = re.compile(r"([+-]?(?:\d+[+*-])*\d+)").findall(s)
  14.  
  15.     maxLenExp = ""
  16.  
  17.     for exp in lst:
  18.         if len(exp) > len(maxLenExp):
  19.             maxLenExp = exp
  20.  
  21.     return maxLenExp
  22.  
  23.  
  24. # 算法入口
  25. def getResult():
  26.     maxLenExp = getMaxLenExp()
  27.  
  28.     if len(maxLenExp) == 0:
  29.         return 0
  30.     else:
  31.         return eval(maxLenExp)
  32.  
  33.  
  34. # 算法调用
  35. print(getResult())

C算法源码

双指针+栈解法
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5. #define MAX_SIZE 10000
  6. #define OPERATOR_NUM_LEN 100
  7. #define OPERATOR_NUM_SIZE 1000
  8.  
  9. char s[MAX_SIZE] = {'\0'};
  10.  
  11. long calcExpStr(const char *exp) {
  12.     // 记录表达式中各块的操作数
  13.     long stack[OPERATOR_NUM_SIZE];
  14.     int stack_size = 0;
  15.  
  16.     // 各块操作数的"值"部分的缓存容器
  17.     char numStr[OPERATOR_NUM_LEN] = {'\0'};
  18.     int numStr_size = 0;
  19.  
  20.     // 各块操作数的"系数"部分，默认为1
  21.     long num_coef = 1;
  22.  
  23.     // 如果合法的表达式可以+或-开头
  24.     char start = exp[0];
  25.     if(start == '+' || start == '-') {
  26.         // 将exp开头的符号去掉
  27.         exp += 1;
  28.     }
  29.  
  30.     if(start == '-') {
  31.         // 如果表达式开头是负号，则开头操作数的系数为-1
  32.         num_coef = -1;
  33.     }
  34.  
  35.  
  36.     int i = 0;
  37.     while (exp[i] != '\0') {
  38.         char c = exp[i];
  39.  
  40.         if (c >= '0' && c <= '9') {
  41.             numStr[numStr_size++] = c;
  42.         } else {
  43.             // 如果扫描到的字符c是运算符，那么该运算符打断了前面操作数的扫描，前面操作数 = 系数 * 值
  44.             long num = num_coef * atol(numStr);
  45.             stack[stack_size++] = num;
  46.  
  47.             // 清空缓存容器，用于下一个操作数的”值“记录
  48.             numStr_size = 0;
  49.             memset(numStr, '\0', OPERATOR_NUM_LEN);
  50.  
  51.             if (c == '+') {
  52.                 // 如果运算符是加法，则后一个操作数的系数为1
  53.                 num_coef = 1;
  54.             } else if (c == '-') {
  55.                 // 如果运算符是减法，则后一个操作数的系数为-1
  56.                 num_coef = -1;
  57.             } else if (c == '*') {
  58.                 // 如果运算符是乘法，则后一个操作数的系数为栈顶值，比如2*3，其中2可以当作3的系数
  59.                 num_coef = stack[--stack_size];
  60.             }
  61.         }
  62.  
  63.         i++;
  64.     }
  65.  
  66.     // 收尾处理
  67.     if (numStr_size > 0) {
  68.         long num = num_coef * atol(numStr);
  69.         stack[stack_size++] = num;
  70.     }
  71.  
  72.     // 表达式分块后，每一块独立计算，所有块的和就是表达式的结果
  73.     long res = 0;
  74.     for (int j = 0; j < stack_size; j++) {
  75.         res += stack[j];
  76.     }
  77.  
  78.     return res;
  79. }
  80.  
  81. int isDigit(char c) {
  82.     return c >= '0' && c <= '9';
  83. }
  84.  
  85. int isOperator(char c) {
  86.     return c == '+' || c == '-' || c == '*';
  87. }
  88.  
  89. int main() {
  90.     gets(s);
  91.  
  92.     // 记录最长合法表达式的长度
  93.     int maxLen = 0;
  94.     // 记录最长合法表达式的起始位置
  95.     int start = -1;
  96.  
  97.     // 双指针找最长合法表达式
  98.     int l = 0;
  99.     int r = 0;
  100.  
  101.     while (s[r] != '\0') {
  102.         // 合法表达式必须以数字开头
  103.         // 如果+-开头的表达式也是合法的表达式，则需要添加当前代码135~138行逻辑
  104.         while (s[l] != '\0' && !isDigit(s[l])) {
  105.             l++;
  106.         }
  107.  
  108.         if (s[l] == '\0') {
  109.             break;
  110.         }
  111.  
  112.         // l找到合法表达式的开头后，r指针扫开始描合法表达式剩余部门
  113.         r = l + 1;
  114.  
  115.         while (s[r] != '\0') {
  116.             // 如果r指针扫描到的是数字字符，则继续扫描
  117.             // 如果r指针扫描到的是+-*符号，则需要看r-1字符是不是+-*符号，如果不是则继续扫描
  118.             if (isDigit(s[r]) || (isOperator(s[r]) && !isOperator(s[r - 1]))) {
  119.                 r++;
  120.             } else {
  121.                 // 其他情况中断r扫描
  122.                 break;
  123.             }
  124.         }
  125.  
  126.         // 此时 [l, r) 左闭右开范围就是合法表达式
  127.         int len = r - l;
  128.  
  129.         // 注意如果r-1位置是+-*符号，则不能包含
  130.         if (isOperator(s[r - 1])) {
  131.             len -= 1;
  132.         }
  133.  
  134.         // 如果认为 +1+2，-2*3 这种也是合法的表达式，则需要加入下面逻辑
  135.         if (l >= 1 && (s[l - 1] == '+' || s[l - 1] == '-')) {
  136.             l--;
  137.             len++;
  138.         }
  139.  
  140.         // 记录最长的合法表达式长度，以及起始位置
  141.         if (len > maxLen) {
  142.             maxLen = len;
  143.             start = l;
  144.         }
  145.  
  146.         // 找到一个合法表达式后，继续找下一个合法表达式
  147.         l = r + 1;
  148.     }
  149.  
  150.     if (start == -1) {
  151.         // 如果没找到合法表达式，则直接打印0
  152.         puts("0");
  153.     } else {
  154.         // 找到最长合法表达式，则计算其结果打印
  155.         s[start + maxLen] = '\0';
  156.         printf("%ld\n", calcExpStr(s + start));
  157.     }
  158.  
  159.     return 0;
  160. }
  161.

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/173431
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号