返回目录

题目描述

提取字符串中的最长合法简单数学表达式，字符串长度最长的，并计算表达式的值。如果没有，则返回 0 。

简单数学表达式只能包含以下内容：

• 0-9数字，符号+-*

说明：

1. 所有数字，计算结果都不超过long
2. 如果有多个长度一样的，请返回第一个表达式的结果
3. 数学表达式，必须是最长的，合法的
4. 操作符不能连续出现，如 +--+1 是不合法的

输入描述

字符串

输出描述

表达式值

示例：

Python算法源码

# 校验字符串exp是否为合法表达式，本题合法表达式可能是：a+b，a*b，a-b，其中操作数a可能带有正负号
def is_valid(exp):
    # 合法表达式开头可以是+,-,数字，如果不是这些字符，则是非法表达式
    if not (exp[0] == '+' or exp[0] == '-' or (exp[0].isdigit())):
        return False

    # 运算符位置
    op_idx = -1

    i = 1
    while i < len(exp):
        c = exp[i]

        # 表达式内容只能是+, -, *, 数字, 如果包含其他字符，则是非法表达式
        if c not in ['+', '-', '*', ''] and not c.isdigit():
            return False

        # 如果是运算符，则记录其出现位置
        if c in ['+', '-', '*']:
            if op_idx != -1:
                # 如果表达式内含有多个运算符，则是非法表达式
                return False
            else:
                op_idx = i

        i += 1

    # 避免 ++123
    if (exp[0] == '+' or exp[0] == '-') and op_idx == 1:
        return False

    # 避免 123+
    if op_idx == i - 1:
        return False

    return op_idx != -1


def main():
    s = input()

    # 最长合法表达式长度
    max_exp_len = 0
    # 最长合法表达式的结果
    ans = 0

    len_s = len(s)

    for i in range(len_s):
        # 本题有大数量级用例，因此需要此步优化，不然通过率不高
        if len_s - i <= max_exp_len:
            break

        for j in range(i, len_s):
            # 截取 [i, j] 范围子串sub
            sub = s[i:j + 1]

            # 判断sub子串是否为合法表达式，若是，则继续看sub子串长度是否比maxLen更长，若是，则找到更长的合法表达式
            sub_len = len(sub)
            if is_valid(sub) and sub_len > max_exp_len:
                max_exp_len = sub_len

                # 找到运算符位置k，k从1开始探索，因为索引0可能是正负号
                k = 1
                while sub[k] != '' and k < len(sub):
                    if sub[k] in ['+', '-', '*']:
                        break
                    else:
                        k += 1

                # 操作数1
                num1 = sub[:k]

                # 运算符
                op = sub[k]

                # 操作数2
                num2 = sub[k + 1:]

                op_num1 = int(num1)
                op_num2 = int(num2)

                if op == '+':
                    ans = op_num1 + op_num2
                elif op == '-':
                    ans = op_num1 - op_num2
                elif op == '*':
                    ans = op_num1 * op_num2

    print(ans)


if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 校验字符串exp是否为合法表达式，本题合法表达式可能是：a+b，a*b，a-b，其中操作数a可能带有正负号
int is_valid_expression(char *expression) {
    // 合法表达式开头可以是+,-,数字，如果不是这些字符，则是非法表达式
    if (!(expression[0] == '+' || expression[0] == '-' || (expression[0] >= '0' && expression[0] <= '9'))) {
        return 0;
    }

    // 运算符位置
    int operator_index = -1;

    int i = 1;
    while (expression[i] != '\0') {
        char c = expression[i];

        // 表达式内容只能是+, -, *, 数字, 如果包含其他字符，则是非法表达式
        if (c != '+' && c != '-' && c != '*' && !(c >= '0' && c <= '9')) {
            return 0;
        }

        // 如果是运算符，则记录其出现位置
        if (c == '+' || c == '-' || c == '*') {
            if (operator_index != -1) {
                // 如果表达式内含有多个运算符，则是非法表达式
                return 0;
            } else {
                operator_index = i;
            }
        }

        i++;
    }

    // 避免 ++123
    if ((expression[0] == '+' || expression[0] == '-') && operator_index == 1) {
        return 0;
    }

    // 避免 123+
    if (operator_index == i - 1) {
        return 0;
    }

    return operator_index != -1;
}

int main() {
    char expression[1000];
    gets(expression);

    // 最长合法表达式长度
    int max_expression_length = 0;
    // 最长合法表达式的结果
    long long result = 0;

    size_t length = strlen(expression);

    int i = 0; // 用于外层循环的索引变量
    while (i < length) {
        int j = i; // 用于内层循环的索引变量
        while (j < length) {
            // 截取 [i, j] 范围子串substring
            char substring[1000] = {'\0'};
            strncpy(substring, expression + i, j - i + 1);

            // 判断substring子串是否为合法表达式，若是，则继续看substring子串长度是否比maxLen更长，若是，则找到更长的合法表达式
            int substring_length = j - i + 1;
            if (is_valid_expression(substring) && substring_length > max_expression_length) {
                max_expression_length = substring_length;

                // 找到运算符位置k，k从1开始探索，因为索引0可能是正负号
                int k = 1;
                while (substring[k] != '\0') {
                    if (substring[k] == '+' || substring[k] == '-' || substring[k] == '*') {
                        break;
                    } else {
                        k++;
                    }
                }

                // 操作数1
                char number1[50] = {'\0'};
                strncpy(number1, substring, k);

                // 运算符
                char operator = substring[k];

                // 操作数2
                char number2[50] = {'\0'};
                strcpy(number2, substring + k + 1);

                long long operand1 = atoll(number1);
                long long operand2 = atoll(number2);

                if (operator == '+') {
                    result = operand1 + operand2;
                } else if (operator == '-') {
                    result = operand1 - operand2;
                } else if (operator == '*') {
                    result = operand1 * operand2;
                }
            }

            j++;
        }

        i++;
    }

    printf("%lld\n", result);

    return 0;
}include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 校验字符串exp是否为合法表达式，本题合法表达式可能是：a+b，a*b，a-b，其中操作数a可能带有正负号
int is_valid_expression(char *expression) {
    // 合法表达式开头可以是+,-,数字，如果不是这些字符，则是非法表达式
    if (!(expression[0] == '+' || expression[0] == '-' || (expression[0] >= '0' && expression[0] <= '9'))) {
        return 0;
    }

    // 运算符位置
    int operator_index = -1;

    int i = 1;
    while (expression[i] != '\0') {
        char c = expression[i];

        // 表达式内容只能是+, -, *, 数字, 如果包含其他字符，则是非法表达式
        if (c != '+' && c != '-' && c != '*' && !(c >= '0' && c <= '9')) {
            return 0;
        }

        // 如果是运算符，则记录其出现位置
        if (c == '+' || c == '-' || c == '*') {
            if (operator_index != -1) {
                // 如果表达式内含有多个运算符，则是非法表达式
                return 0;
            } else {
                operator_index = i;
            }
        }

        i++;
    }

    // 避免 ++123
    if ((expression[0] == '+' || expression[0] == '-') && operator_index == 1) {
        return 0;
    }

    // 避免 123+
    if (operator_index == i - 1) {
        return 0;
    }

    return operator_index != -1;
}

int main() {
    char expression[1000];
    gets(expression);

    // 最长合法表达式长度
    int max_expression_length = 0;
    // 最长合法表达式的结果
    long long result = 0;

    size_t length = strlen(expression);

    int i = 0; // 用于外层循环的索引变量
    while (i < length) {
        int j = i; // 用于内层循环的索引变量
        while (j < length) {
            // 截取 [i, j] 范围子串substring
            char substring[1000] = {'\0'};
            strncpy(substring, expression + i, j - i + 1);

            // 判断substring子串是否为合法表达式，若是，则继续看substring子串长度是否比maxLen更长，若是，则找到更长的合法表达式
            int substring_length = j - i + 1;
            if (is_valid_expression(substring) && substring_length > max_expression_length) {
                max_expression_length = substring_length;

                // 找到运算符位置k，k从1开始探索，因为索引0可能是正负号
                int k = 1;
                while (substring[k] != '\0') {
                    if (substring[k] == '+' || substring[k] == '-' || substring[k] == '*') {
                        break;
                    } else {
                        k++;
                    }
                }

                // 操作数1
                char number1[50] = {'\0'};
                strncpy(number1, substring, k);

                // 运算符
                char operator = substring[k];

                // 操作数2
                char number2[50] = {'\0'};
                strcpy(number2, substring + k + 1);

                long long operand1 = atoll(number1);
                long long operand2 = atoll(number2);

                if (operator == '+') {
                    result = operand1 + operand2;
                } else if (operator == '-') {
                    result = operand1 - operand2;
                } else if (operator == '*') {
                    result = operand1 * operand2;
                }
            }

            j++;
        }

        i++;
    }

    printf("%lld\n", result);

    return 0;
}

Java算法源码

import java.util.Li

import java.util.Scanner;

public class Main {
  
    // 校验字符串exp是否为合法表达式，本题合法表达式可能是：a+b，a*b，a-b，其中操作数a可能带有正负号
    static boolean isValid(String exp) {
        // 合法表达式开头可以是+,-,数字，如果不是这些字符，则是非法表达式
        if (!(exp.charAt(0) == '+' || exp.charAt(0) == '-' || (exp.charAt(0) >= '0' && exp.charAt(0) <= '9'))) {
            return false;
        }
 
        // 运算符位置
        int opIdx = -1;
 
        for (int i = 1; i < exp.length(); i++) {
            char c = exp.charAt(i);
 
            // 表达式内容只能是+, -, *, 数字, 如果包含其他字符，则是非法表达式
            if (c != '+' && c != '-' && c != '*' && !(c >= '0' && c <= '9')) {
                return false;
            }
 
            // 如果是运算符，则记录其出现位置
            if (c == '+' || c == '-' || c == '*') {
                if (opIdx != -1) {
                    // 如果表达式内含有多个运算符，则是非法表达式
                    return false;
                } else {
                    opIdx = i;
                }
            }
        }
 
        // 避免 ++123
        if ((exp.charAt(0) == '+' || exp.charAt(0) == '-') && opIdx == 1) {
            return false;
        }
 
        // 避免 123+
        if (opIdx == exp.length() - 1) {
            return false;
        }
 
        return opIdx != -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String s = sc.nextLine();
 
        // 最长合法表达式长度
        int maxExpLen = 0;
        // 最长合法表达式的结果
        long ans = 0;
 
        int len = s.length();
 
        for (int i = 0; i < len; i++) {
 
            // 本题有大数量级用例，因此需要此步优化，不然通过率不高
            if (len - i <= maxExpLen) {
                break;
            }
 
            for (int j = i; j < len; j++) {
                // 截取 [i, j] 范围子串sub
                String sub = s.substring(i, j + 1);
 
                // 判断sub子串是否为合法表达式，若是，则继续看sub子串长度是否比maxLen更长，若是，则找到更长的合法表达式
                int subLen = j - i + 1;
                if (isValid(sub) && subLen > maxExpLen) {
                    maxExpLen = subLen;
 
                    // 找到运算符位置k，k从1开始探索，因为索引0可能是正负号
                    int k = 1;
                    while (sub.charAt(k) != '\0') {
                        if (sub.charAt(k) == '+' || sub.charAt(k) == '-' || sub.charAt(k) == '*') {
                            break;
                        } else {
                            k++;
                        }
                    }
 
                    // 操作数1
                    String num1 = sub.substring(0, k);
 
                    // 运算符
                    char op = sub.charAt(k);
 
                    // 操作数2
                    String num2 = sub.substring(k + 1);
 
                    long opNum1 = Long.parseLong(num1);
                    long opNum2 = Long.parseLong(num2);
 
                    if (op == '+') {
                        ans = opNum1 + opNum2;
                    } else if (op == '-') {
                        ans = opNum1 - opNum2;
                    } else if (op == '*') {
                        ans = opNum1 * opNum2;
                    }
                }
            }
        }
 
        System.out.println(ans);
    }
}