返回目录
题目描述
提取字符串中的最长合法简单数学表达式,字符串长度最长的,并计算表达式的值。如果没有,则返回 0 。
简单数学表达式只能包含以下内容:
- 0-9数字,符号+-*
说明:
- 所有数字,计算结果都不超过long
- 如果有多个长度一样的,请返回第一个表达式的结果
- 数学表达式,必须是最长的,合法的
- 操作符不能连续出现,如 +--+1 是不合法的
输入描述
字符串
输出描述
表达式值
示例:
输入 | 1-2abcd |
---|---|
输出 | -1 |
说明 | 最长合法简单数学表达式是"1-2",结果是-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);
}
}
6 条评论
def isValid(str):
if not(str[0] in ['+', '-'] or str[0].isdigit()):
return False, -1
op_index = -1
for i in range(1,len(str)):
if str[i] not in ['+','-','*',' '] and not str[i].isdigit(): # 包含其他字符
return False, op_index
if str[i] in ['+','-','*']:
if op_index != -1: # 防止多个符号。比如4+5+5。第一次出现运算符就给op_index赋值了,再碰到直接返回False
return False, op_index
else:
op_index = i
if str[0] in ['+','-'] and op_index == 1: # 防止--5,++6等
return False, op_index
if op_index == len(str) -1: # 防止456+,7-等
return False, op_index
return True, op_index
def main():
str_list = input()
max_len = 0
max_str = ''
op_index = -1
first_num_tag = 1
for i in range(len(str_list)):
for j in range(i,len(str_list)):
if j+1 - i max_len:
max_len = j+1 - i
max_str = str_list[i:j+1]
op_index = index
if max_str[0] == '+':
max_str = max_str[1:]
op_index -= 1
elif max_str[0] == '-':
first_num_tag = -1
max_str = max_str[1:]
op_index -= 1
first_num = int(max_str[:op_index]) * first_num_tag
second_num = int(max_str[op_index+1:])
if max_str[op_index] == '*':
res = first_num * second_num
elif max_str[op_index] == '+':
res = first_num + second_num
else:
res = first_num - second_num
print(res)
if __name__ == '__main__':
main()
[...]2024 C卷 100分序号题目知 识 点难易程度1密码输入检测数据结构/栈☆☆☆2分配土地几何问题☆☆☆3找座位逻辑分析☆☆☆4智能成绩表动态条件分析☆☆☆5内存冷热标记多条件排序☆☆☆6螺旋数字矩阵逻辑分析☆☆☆7围棋的气逻辑分析☆☆☆8分割平衡字符串逻辑分析☆☆☆9机器人搬砖二分法☆☆☆10转盘寿司数据结构/栈/单调栈☆☆☆11小明找位置二分法☆☆☆12提取字符串的最长合法简单数学表达式双指[...]
[...]2024 C卷 100分序号题目知 识 点难易程度1密码输入检测数据结构/栈☆☆☆2分配土地几何问题☆☆☆3找座位逻辑分析☆☆☆4智能成绩表动态条件分析☆☆☆5内存冷热标记多条件排序☆☆☆6螺旋数字矩阵逻辑分析☆☆☆7围棋的气逻辑分析☆☆☆8分割平衡字符串逻辑分析☆☆☆9机器人搬砖二分法☆☆☆10转盘寿司数据结构/栈/单调栈☆☆☆11小明找位置二分法☆☆☆12提取字符串的最长合法简单数学表达式双指[...]
[...]2024 C卷 100分序号题目知 识 点难易程度1密码输入检测数据结构/栈☆☆☆2分配土地几何问题☆☆☆3找座位逻辑分析☆☆☆4智能成绩表动态条件分析☆☆☆5内存冷热标记多条件排序☆☆☆6螺旋数字矩阵逻辑分析☆☆☆7围棋的气逻辑分析☆☆☆8分割平衡字符串逻辑分析☆☆☆9机器人搬砖二分法☆☆☆10转盘寿司数据结构/栈/单调栈☆☆☆11小明找位置二分法☆☆☆12提取字符串的最长合法简单数学表达式双指[...]
[...]2024 C卷 100分序号题目知 识 点难易程度1密码输入检测数据结构/栈☆☆☆2分配土地几何问题☆☆☆3找座位逻辑分析☆☆☆4智能成绩表动态条件分析☆☆☆5内存冷热标记多条件排序☆☆☆6螺旋数字矩阵逻辑分析☆☆☆7围棋的气逻辑分析☆☆☆8分割平衡字符串逻辑分析☆☆☆9机器人搬砖二分法☆☆☆10转盘寿司数据结构/栈/单调栈☆☆☆11小明找位置二分法☆☆☆12提取字符串的最长合法简单数学表达式双指[...]
[...]真题目录序号题目 1密码输入检测 2分配土地 3找座位 4智能成绩表 5内存冷热标记 6螺旋数字矩阵 机器人搬砖 转盘寿司 提取字符串的最长合法简单数学表达式 2最富裕的小家庭 3最长字符串的长度(一) 开源项目热度榜单 游戏分组 虚拟理财游戏[...]