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+([