【栈】2024D-密码输入检测

[P2605] 【栈】2024D-密码输入检测

本题练习地址：https://www.algomooc.com/problem/P2605

题目描述

给定用户密码输入流 input，输入流中字符'<'表示退格，可以清除前一个输入的字符，请你编写程序，输出最终得到的密码字符，并判断密码是否满足如下的密码安全要求。

密码安全要求如下：

1. 密码长度>=8;
2. 密码至少需要包含 1 个大写字母;
3. 密码至少需要包含 1 个小写字母;
4. 密码至少需要包含 1 个数字;
5. 密码至少需要包含 1 个字母和数字以外的非空白特殊字符

注意空串退格后仍然为空串，且用户输入的字符串不包含'<'字符和空白字符。

输入描述

用一行字符串表示输入的用户数据，输入的字符串中'<'字符标识退格，用户输入的字符串不包含空白字符，例如：ABC<c89%000<

输出描述

输出经过程序处理后，输出的实际密码字符串，并输出改密码字符串是否满足密码安全要求。两者间由','分隔， 例如：ABc89%00,true

示例

输入

ABC<c89%000<

输出

ABc89%00,true

解题思路

本题分为两个步骤：

1. 对输入的密码进行退格处理，这显然可以使用栈来完成。
2. 对处理完毕之后的密码进行各个条件的判断，直接调用各种字符串相关的API即可完成。

代码

Python

# 题目：【栈】2023C-密码输入检测
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：栈
# 代码看不懂的地方，请直接在群上提问


s = input()
stack = list()
# 遍历字符串s中的每一个字符ch
for ch in s:
    # 如果不是退格，则直接入栈
    if ch != "<":
        stack.append(ch)
    # 如果遇到退格，且栈不为空栈，弹出栈顶元素表示退格
    elif ch == "<" and len(stack) > 0:
        stack.pop()

# 重新合并栈中的所有元素，得到处理后的字符串s_new
s_new = "".join(stack)

# 对字符串s_new进行每一个条件的判断
# 判断1：长度是否大于等于8
flag1 = len(s_new) >= 8
# 判断2：是否存在大写字符
flag2 = any(ch.isupper() for ch in s_new)
# 判断3：是否存在小写字符
flag3 = any(ch.islower() for ch in s_new)
# 判断4：是否存在数字
flag4 = any(ch.isdigit() for ch in s_new)
# 判断5：是否存在除了字符串、数字、空格之外的特殊字符
flag5 = any(not ch.isalnum() and not ch.isspace() for ch in s_new)

# 若上述五个条件均为True，则输出字符串和true
if flag1 and flag2 and flag3 and flag4 and flag5:
    print(f"{s_new},true")
# 否则输出字符串和false
else:
    print(f"{s_new},false")

Java

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();

        Stack<Character> stack = new Stack<>();
        for (char ch : s.toCharArray()) {
            if (ch != '<') {
                stack.push(ch);
            } else if (ch == '<' && !stack.isEmpty()) {
                stack.pop();
            }
        }

        StringBuilder sNew = new StringBuilder();
        while (!stack.isEmpty()) {
            sNew.insert(0, stack.pop());
        }

        boolean flag1 = sNew.length() >= 8;
        boolean flag2 = false, flag3 = false, flag4 = false, flag5 = false;

        for (char ch : sNew.toString().toCharArray()) {
            if (Character.isUpperCase(ch)) {
                flag2 = true;
            } else if (Character.isLowerCase(ch)) {
                flag3 = true;
            } else if (Character.isDigit(ch)) {
                flag4 = true;
            } else if (!Character.isLetterOrDigit(ch) && !Character.isWhitespace(ch)) {
                flag5 = true;
            }
        }

        if (flag1 && flag2 && flag3 && flag4 && flag5) {
            System.out.println(sNew.toString() + ",true");
        } else {
            System.out.println(sNew.toString() + ",false");
        }
    }
}

C++

#include <iostream>
#include <stack>
#include <cctype>

int main() {
    std::string s;
    std::cin >> s;

    std::stack<char> stack;
    for (char ch : s) {
        if (ch != '<') {
            stack.push(ch);
        } else if (ch == '<' && !stack.empty()) {
            stack.pop();
        }
    }

    std::string s_new;
    while (!stack.empty()) {
        s_new = stack.top() + s_new;
        stack.pop();
    }

    bool flag1 = s_new.length() >= 8;
    bool flag2 = false, flag3 = false, flag4 = false, flag5 = false;

    for (char ch : s_new) {
        if (isupper(ch)) {
            flag2 = true;
        } else if (islower(ch)) {
            flag3 = true;
        } else if (isdigit(ch)) {
            flag4 = true;
        } else if (!isalnum(ch) && !isspace(ch)) {
            flag5 = true;
        }
    }

    if (flag1 && flag2 && flag3 && flag4 && flag5) {
        std::cout << s_new << ",true" << std::endl;
    } else {
        std::cout << s_new << ",false" << std::endl;
    }

    return 0;
}

时空复杂度

时间复杂度：O(N)。处理字符串每个字符串仅需遍历一遍。五次判断，需要均需要遍历一次s_new。总体时间复杂度为O(6N)=O(N)

空间复杂度：O(1)。仅需若干常数变量。