(新卷,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*3102我们需要注意表达式运算符优先级问题即先乘后加减相同优先级的运算从左到右进行。这里我的思路是将 合法表达式串 进行分块比如上面表达式可以分为1-2*3102我们可以发现、-运算符前面的操作数都是独立成块比如上面表达式的操作数110* 运算符前面的操作数则需要组合成块比如上面表达式的操作数2后面是 * 运算符因此 2 需要和 3 进行组合。分块之后我们只需要求各块结果之和即可。具体逻辑实现如下首先定义一个栈stack用于保存各个块的结果其次定义一个块的值容器numStr用于临时缓存分块的值最后定义一个块的系数变量numCoef用于临时缓存分块的系数扫描合法表达式串如果当前扫描的字符c是c 是数字则直接缓存进块的值容器numStr中c 是 号则打断前一个操作数的收集此时我们应该将前一个操作数计算结果后加入到stack中操作数 int(numStr) * numCoef同时更新numCoef 1因为c是号所以后一个操作数的系数为1c 是 - 号则打断前一个操作数的收集此时我们应该将前一个操作数计算结果后加入到stack中操作数 int(numStr) * numCoef同时更新numCoef -1因为c是-号所以后一个操作数的系数为-1c 是 * 号则打断前一个操作数的收集并且 * 前后的两个操作数需要组合而 * 前面的操作数记录在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; // 记录表达式中各块的操作数 LinkedListLong 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; }