- 提取字符串中的最长数学表达式（Java JS Python C）)
(新卷,100分)- 提取字符串中的最长数学表达式（Java & JS & Python & C）
题目描述
提取字符串中的最长合法简单数学表达式，字符串长度最长的，并计算表达式的值。如果没有，则返回 0 。
简单数学表达式只能包含以下内容：
- 0-9数字，符号+-*
说明：
- 所有数字，计算结果都不超过long
- 如果有多个长度一样的，请返回第一个表达式的结果
- 数学表达式，必须是最长的，合法的
- 操作符不能连续出现，如 +--+1 是不合法的
输入描述
字符串
输出描述
表达式值
用例
| 输入 | 1-2abcd |
| 输出 | -1 |
| 说明 | 最长合法简单数学表达式是"1-2"，结果是-1 |
题目解析
注意！！！本题原题描述中没有 / 除号
因此，本题的合法表达式不需要考虑 '/' 号，也就不用考虑除0，以及除法是整除还是小数除的问题。
另外，本题的 +、-号仅作为运算符号，不作为正负号。因此 "+1"，"-1" 这种不能理解为合法的表达式。
本题可以分为两步求解：
- 找出输入串中最长合法的表达式
- 计算最长合法表达式的结果
关于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 中，即 * 前面的操作数，可以当初 * 后面操作数的系数
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) { 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; 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 calcExpStr(maxLenExp); } } function getMaxLenExp(s) { 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) { return eval(exp); }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) { 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; 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 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(): 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 calcExpStr(exp): return eval(exp) # 获取最长合法表达式 def getMaxLenExp(): 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())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; 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') { // 合法表达式必须以数字开头 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; } // 记录最长的合法表达式长度，以及起始位置 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; }- 单词接龙（Java JS Python）)
- 第k个排列（Java JS Python）)
