2024年华为OD机试真题-提取字符串中的最长数学表达式
华为OD机试真题-提取字符串中的最长数学表达式并计算-2024年OD统一考试(D卷)
题目描述:
提取字符串中的最长合法简单数学表达式,字符串长度最长的,并计算表达式的值。如果没有,则返回0
简单数学表达式只能包含以下内容
0-9数字,符号 +-*
说明:
1. 所有数字,计算结果都不超过long
2. 如果有多个长度一样的,请返回第一个表达式的结果
3. 数学表达式,必须是最长的,合法的
4. 操作符不能连续出现,如 +--+1 是不合法的
输入描述:
字符串
输出描述:
表达式值
补充说明:
示例1
输入:
1-2abcd输出:
-1说明:
解题思路:
从一个字符串中提取最长的合法简单数学表达式并计算其值,但点在于会正则表达式和简单的模拟运算,我们可以分步进行。以下是详细的解题思路:
第一步:理解和定义合法的数学表达式
1. 表达式组成:合法的简单数学表达式应仅包含数字(0-9)和运算符(+,-,*)。
2. 操作符限制:不允许操作符连续出现,如 ++, +-, -- 等是非法的。
3. 数学表达式格式:一个合法的表达式可以是单个数字,或者是由操作符连接的一系列数字,如 123, -123, 100+200-50*2。
第二步:提取所有可能的合法表达式
1.使用正则表达式:通过正则表达式来匹配和提取字符串中的所有可能的合法表达式。这一步骤是关键,需要确保正则表达式正确地定义以符合合法表达式的格式要求。
2. 正则表达式设计:表达式应该能匹配一个数字,以及后面可能跟随的由操作符和数字组成的序列
第三步:从匹配结果中找出最长的表达式
1. 遍历匹配结果:检查所有通过正则表达式找到的匹配项,记录下最长的一个。如果有多个长度相同的表达式,只保留第一个找到的。
第四步:计算找到的最长表达式的值
1. 表达式求值:编写一个函数来计算数学表达式的值。这个函数需要能够处理加法、减法和乘法,并正确地按照运算符的优先级来计算(在这个问题中,由于只涉及简单运算,可以逐个处理运算符)。
2. 使用栈进行计算:对于涉及加法和乘法的表达式,可以使用栈来辅助计算,以确保乘法运算可以在加减运算之前处理。
第五步:处理边界情况
1. 无合法表达式:如果字符串中不存在任何合法的数学表达式,应返回 0。
Java解法:
import java.util.Scanner; import java.util.Stack; import java.util.regex.Matcher; import java.util.regex.Pattern; public class Main { // 功能:计算简单数学表达式的值 public static long evaluateExpression(String expression) { if (expression.isEmpty()) return 0; // 如果表达式为空,返回 0 Stack<Long> values = new Stack<>(); // 使用栈来存储中间结果 long currentNumber = 0; // 当前解析的数字 char sign = '+'; // 当前数字前的操作符,默认为 '+' expression += "+"; // 在表达式末尾追加 '+' for (int i = 0; i < expression.length(); i++) { char c = expression.charAt(i); if (Character.isDigit(c)) { // 如果字符是数字 currentNumber = currentNumber * 10 + (c - '0'); // 累加形成整数 } else if (c == '+' || c == '-' || c == '*' || i == expression.length() - 1) { // 如果字符是操作符或已达字符串末尾 if (c != '*' && !values.isEmpty() && values.peek() == -1) { values.pop(); // 如果栈顶为 -1(之前的符号为减号),则弹出 sign = '-'; // 将符号改为负号 } switch (sign) { case '+': values.push(currentNumber); // 加法:将当前数字压入栈 break; case '-': values.push(-currentNumber); // 减法:将当前数字的负值压入栈 break; case '*': long top = values.pop(); // 取出栈顶元素 values.push(top * currentNumber); // 执行乘法并将结果压回栈 break; } currentNumber = 0; // 重置当前数字 sign = c; // 更新操作符 } } long result = 0; // 初始化结果 while (!values.empty()) { result += values.pop(); // 将栈中所有数字累加 } return result; // 返回计算结果 } // 功能:提取最长的合法数学表达式并计算其值 public static long findAndEvaluate(String s) { Pattern expRegex = Pattern.compile("(\\d+)([\\*+-]\\d+)*"); // 定义正则表达式,匹配数字和操作符序列 Matcher matcher = expRegex.matcher(s); String longestValidExpression = ""; int maxLength = 0; while (matcher.find()) { String matchStr = matcher.group(); // 获取匹配的字符串 if (matchStr.length() > maxLength && matchStr.matches("^(-?\\d+([
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024年OD统一考试(D卷),最新最完整题库。 收录130+道真题,提供解题思路,Java/Python/C++三种答案源码。