华为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
 * <p>
 * 简单数学表达式只能包含以下内容：
 * <p>
 * 0-9数字，符号+-*
 * 说明：
 * <p>
 * 所有数字，计算结果都不超过long
 * 如果有多个长度一样的，请返回第一个表达式的结果
 * 数学表达式，必须是最长的，合法的
 * 操作符不能连续出现，如 +--+1 是不合法的
 * 输入描述
 * 字符串
 * <p>
 * 输出描述
 * 表达式值
 */
// 注意类名必须为 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
 * <p>
 * 简单数学表达式只能包含以下内容：
 * <p>
 * 0-9数字，符号+-*
 * 说明：
 * <p>
 * 所有数字，计算结果都不超过long
 * 如果有多个长度一样的，请返回第一个表达式的结果
 * 数学表达式，必须是最长的，合法的
 * 操作符不能连续出现，如 +--+1 是不合法的
 * 输入描述
 * 字符串
 * <p>
 * 输出描述
 * 表达式值
 */
// 注意类名必须为 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();
        }
    }
}