华为OD刷题C卷 – 每日刷题 23（提取字符串中的最长表达式，模拟目录管理功能 – 完整实现）
1、提取字符串中的最长表达式
目标是从一个给定的字符串中提取出最长的合法简单数学表达式，并计算该表达式的值。如果存在多个同样长度的合法表达式，则选择第一个出现的表达式进行计算。
简单数学表达式的规则：
只包含0-9的数字和+、-、*三种运算符。
所有数字的计算结果不超过long类型的最大值。
表达式中操作符不能连续出现，例如”±-+1″是非法的。
如果有多个相同长度的合法表达式，选择第一个出现的表达式。
表达式必须是最长的合法表达式。
2、（模拟目录管理功能 – 完整实现）：
这段 Java 代码是模拟目录管理功能的完整实现。它定义了 Main 类和两个辅助类 TreeNode 与 Tree。Tree 类包含了目录树的数据结构和基本操作，如创建目录、切换目录和获取当前路径。
main 方法处理标准输入中的命令序列，并根据命令更新目录树的状态，最终输出最后一条命令的执行结果。
// Hard.java
package OD340;
import java.util.Scanner;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
* @description 提取字符串中的最长表达式
* @level 7
* @score 100
* @type 双指针、正则表达式、栈
*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Hard {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
System.out.println(getMaxMath(str));
}
//提取字符串中最长合法表达式并计算值(只包含两个操作数的，且第一个数带正负号)，如有多个长度一样，则返回第一个
public static long getMaxMath(String str) {
char[] chars = str.toCharArray();
int n = chars.length;
//创建正则 匹配 (带正负号0个或1个) 数字1个或多个，然后是 + - * 必须1个 ，然后是 (不带正负号的数字)1个或多个
//Pattern pattern = Pattern.compile("^([+-]?\d+)([+*-]{1}\d+)$");
//如果匹配不只两个操作数
Pattern pattern = Pattern.compile("^([+-]?\d+)(([+*-]\d+)+)([+*-]\d+)$");
int max = 0;
long sum = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
String sub = str.substring(i, j + 1);
Matcher matcher = pattern.matcher(sub);
//如果匹配成功，且长度大于当前保存的最长，则更新
if (matcher.find() && sub.length() > max) {
max = sub.length();
sum = cal(sub);
}
}
}
return sum;
}
//计算合法且无括号表达式的值：如 1 + 2 * 3 返回 7
public static long cal(String str) {
char[] chars = str.toCharArray();
int n = chars.length;
//存放操作数
Stack<Long> stack = new Stack<>();
//初始化符号和数字
long number = 0;
char sign = '+';
//默认符号为"+" 即使第一位是-1 会+0 再 -1
for (int i = 0; i < n; i++) {
char c = chars[i];
//如果遇到数字，拼数字
if (c >= '0' && c <= '9') {
number = number * 10 + (c - '0');
}
//没有括号和空格等不合法行为
//遇到符号或已经到最后一位，将数字入栈、并刷新符号和数字
if (!Character.isDigit(c) || i == n - 1) {
if (sign == '+') {
//该数字前面符号是“+”直接入栈
stack.push(number);
} else if (sign == '-') {
//该数字前面的符号是“-”，变负数后入栈
stack.push(-1 * number);
} else if (sign == '*') {
//该数字前面是乘，弹出一个相乘后再入栈
stack.push(stack.pop() * number);
}
//刷新符号
sign = c;
//刷新数字
number = 0;
}
}
//将栈中的操作数求和
long sum = 0;
for (long i : stack) {
sum += i;
}
return sum;
}
}
// Main.java
package OD340;
import java.util.Scanner;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
* @description 提取字符串中的最长表达式
* @level 7
* @score 100
* @type 双指针、正则表达式、栈
*/
/**
* 题目描述
* 提取字符串中的最长合法简单数学表达式，字符串长度最长的，并计算表达式的值。如果没有，则返回 0
*
* 简单数学表达式只能包含以下内容：
*
* 0-9数字，符号+-*
* 说明：
*
* 所有数字，计算结果都不超过long
* 如果有多个长度一样的，请返回第一个表达式的结果
* 数学表达式，必须是最长的，合法的
* 操作符不能连续出现，如 +--+1 是不合法的
* 输入描述
* 字符串
*
* 输出描述
* 表达式值
*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
System.out.println(getMaxMath(str));
}
//提取字符串中最长合法表达式并计算值(只包含两个操作数的，且第一个数带正负号)，如有多个长度一样，则返回第一个
public static long getMaxMath(String str) {
char[] chars = str.toCharArray();
int n = chars.length;
//创建正则 匹配 (带正负号0个或1个) 数字1个或多个，然后是 + - * 必须1个 ，然后是 (不带正负号的数字)1个或多个
Pattern pattern = Pattern.compile("^([+-]?\d+)([+*-]{1}\d+)$");
//如果匹配不只两个操作数
int max = 0;
long sum = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
String sub = str.substring(i, j + 1);
Matcher matcher = pattern.matcher(sub);
//如果匹配成功，且长度大于当前保存的最长，则更新
if (matcher.find() && sub.length() > max) {
max = sub.length();
sum = cal(sub);
}
}
}
return sum;
}
//计算合法且无括号表达式的值：如 1 + 2 * 3 返回 7
public static long cal(String str) {
char[] chars = str.toCharArray();
int n = chars.length;
//存放操作数
Stack<Long> stack = new Stack<>();
//初始化符号和数字
long number = 0;
char sign = '+';
//默认符号为"+" 即使第一位是-1 会+0 再 -1
for (int i = 0; i < n; i++) {
char c = chars[i];
//如果遇到数字，拼数字
if (c >= '0' && c <= '9') {
number = number * 10 + (c - '0');
}
//没有括号和空格等不合法行为
//遇到符号或已经到最后一位，将数字入栈、并刷新符号和数字
if (!Character.isDigit(c) || i == n - 1) {
if (sign == '+') {
//该数字前面符号是“+”直接入栈
stack.push(number);
} else if (sign == '-') {
//该数字前面的符号是“-”，变负数后入栈
stack.push(-1 * number);
} else if (sign == '*') {
//该数字前面是乘，弹出一个相乘后再入栈
stack.push(stack.pop() * number);
}
//刷新符号
sign = c;
//刷新数字
number = 0;
}
}
//将栈中的操作数求和
long sum = 0;
for (long i : stack) {
sum += i;
}
return sum;
}
}
// Simple.java
package OD340;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
* @description 简单版
* @level 7
* @score 100
* @type 双指针、正则表达式、栈
*/
/**
* 题目描述
* 提取字符串中的最长合法简单数学表达式，字符串长度最长的，并计算表达式的值。如果没有，则返回 0
*
* 简单数学表达式只能包含以下内容：
*
* 0-9数字，符号+-*
* 说明：
*
* 所有数字，计算结果都不超过long
* 如果有多个长度一样的，请返回第一个表达式的结果
* 数学表达式，必须是最长的，合法的
* 操作符不能连续出现，如 +--+1 是不合法的
* 输入描述
* 字符串
*
* 输出描述
* 表达式值
*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Simple {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
//简单合法表达式为只有两个操作数 如 1+1 -1+1 +1+1都是合法的
//正则包含三部分：开头^(含有0个或1个符号的数字1个到多个) (操作符+-*) (数字1个到多个)$结尾
Pattern pattern = Pattern.compile("^([+-]?\d+)([+*-])(\d+)$");
int maxLength = 0;
long sum = 0;
//遍历
for (int i = 0; i < str.length(); i++) {
for (int j = i; j < str.length(); j++) {
String sub = str.substring(i, j + 1);
Matcher matcher = pattern.matcher(sub);
//如果匹配到且长度大于当前保存的长度，则更新
if (matcher.find() && sub.length() > maxLength) {
maxLength = sub.length();
//求解 使用matcher.group(1)和matcher.group(3)分别获取两个数字
long num1 = Long.parseLong(matcher.group(1));
long num2 = Long.parseLong(matcher.group(3));
//操作符
String sign = matcher.group(2);
switch (sign) {
case "+":
sum = num1 + num2;
break;
case "-":
sum = num1 - num2;
break;
case "*":
sum = num1 * num2;
break;
}
}
}
}
System.out.println(sum);
}
}
package OD341;
import java.util.HashMap;
import java.util.Scanner;
/**
* @description 模拟目录管理功能
* @level 6
* @score 200
* @url https://hydro.ac/d/HWOD2023/p/OD341
*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//初始化目录树
Tree tree = new Tree();
//记录最后一条命令的输出 除了pwd有输出，其他都输出空
//输出为空时要输出根目录"/" 才能百分百解法
String command_output = "/";
outer:
while (sc.hasNextLine()) {
String line = sc.nextLine();
String[] tmp = line.split(" ");
//命令 mkdir cd pwd
String cmd_key = tmp[0];
//参数
//String cmd_val = tmp[1];//pwd没有参数，可能会越界
//常量在前面，防止空指针异常
if ("pwd".equals(cmd_key)) {
//pwd不需要参数，有参数的错误输入什么都不需要干
if (tmp.length != 1) continue;
//否则，就将当前命令的输出结果保存
command_output = tree.pwd();
} else if ("mkdir".equals(cmd_key) || "cd".equals(cmd_key)) {
//参数只能有1个
if (tmp.length != 2) continue;
//目录名
String cmd_val = tmp[1];
//除了 cd .. 不需要检测 其他都需要检测文件名是否合法
if (!(cmd_key.equals("cd") && cmd_val.equals(".."))) {
for (int i = 0; i < cmd_val.length(); i++) {
char c = cmd_val.charAt(i);
//不合法，直接跳到下一个命令
if (c < 'a' || c > 'z') continue outer;
}
}
//实现操作
if ("mkdir".equals(cmd_key)) {
tree.mkdir(cmd_val);
//mkdir操作没有输出，清空当前保存的最后输出
command_output = "/";
} else {
//cd
tree.cd(cmd_val);
//清空
command_output = "/";
}
}
}
//输出最后一条命令的输入，如果是mkdir cd 则没有输出
System.out.println(command_output);
}
//节点 包含父目录 子目录
static class TreeNode {
//目录名
String curDicName;
//父目录
TreeNode fa;
//子目录：
HashMap<String, TreeNode> ch;
//构造方法 新建一个节点
public TreeNode(String curDicName, TreeNode fa) {
this.curDicName = curDicName;
this.fa = fa;
this.ch = new HashMap<>();
}
}
//目录树
static class Tree {
//根节点
TreeNode root;
//当前层
TreeNode cur;
//默认无参构造方法
public Tree() {
//根节点 视为名称为/
this.root = new TreeNode("/", null);
this.cur = root;
}
//新建目录
public void mkdir(String dicName) {
//如果有同名子目录，则不做任务操作
//子目录名，子目录对象(名称+"/",该子目录的父目录)
this.cur.ch.putIfAbsent(dicName, new TreeNode(dicName + "/", this.cur));
}
//进入目录
public void cd(String dicName) {
//cd .. 防止空指针异常
if ("..".equals(dicName)) {
//如果上层不为空，则进入上层
if (this.cur.fa != null) {
this.cur = this.cur.fa;
}
//如果为空，不进行任何操作
} else {
//cd dicName
//有同名子目录才进入
if (this.cur.ch.containsKey(dicName)) {
//进入
this.cur = this.cur.ch.get(dicName);
}
//没有同名子目录则不做任何操作
}
}
//pwd
public String pwd() {
StringBuilder sb = new StringBuilder();
//从当前层遍历到root，每次插入到头部，即倒序
TreeNode cur = this.cur;
while (cur != null) {
// c/ -> b/c/ -> a/b/c/ -> /a/b/c/
sb.insert(0, cur.curDicName);
cur = cur.fa;
}
return sb.toString();
}
}
}
