能否利用Stack实现Dictionary同等功能？HTML标签嵌套深度作业问询

Absolutely! You can absolutely implement a Stack-based solution that provides similar functionality to a Dictionary for measuring HTML tag nesting depth—let’s break this down step by step, since you’re focusing on learning Stack and ArrayList instead of taking the easy Dictionary route.

Core Idea #

A Stack is perfect for tracking nested structures (since HTML tags follow a LIFO/last-in-first-out pattern: the most recently opened tag is the first to be closed). To mimic a Dictionary’s key-value pairing (tag name → nesting depth), we just need to store pairs of tag names and their corresponding depths in the Stack. An ArrayList can help us keep a permanent record of all tag-depth pairs if we need to look up depths later, just like you’d query a Dictionary.

Step-by-Step Implementation #

Let’s use Java for this example (the logic translates easily to other languages like Python too):

1. Create a Simple Container Class

First, we need a way to store both the tag name and its depth. A custom class is cleaner than using nested lists for this purpose:

class TagDepth {
    String tagName;
    int depth;

    public TagDepth(String tagName, int depth) {
        this.tagName = tagName;
        this.depth = depth;
    }
}

2. Set Up Your Stack and ArrayList

• The Stack<TagDepth> will track the current nested tag hierarchy (so we know what depth the next tag should be).
• The ArrayList<TagDepth> will act like a persistent Dictionary, storing every tag’s depth so we can look it up later.

3. Process HTML Tags

Loop through your parsed HTML tags (we’ll assume you’ve already split the HTML into individual start/end tags for simplicity):

import java.util.Stack;
import java.util.ArrayList;

public class HtmlNestingTracker {
    public static void main(String[] args) {
        // Simulate a list of parsed HTML tags
        String[] htmlTags = {"<div>", "<p>", "<span>", "</span>", "</p>", "<ul>", "<li>", "</li>", "</ul>", "</div>"};

        Stack<TagDepth> tagStack = new Stack<>();
        ArrayList<TagDepth> tagDepthLog = new ArrayList<>();
        int maxNestingDepth = 0;

        for (String tag : htmlTags) {
            if (tag.startsWith("</")) {
                // Handle closing tag: pop the last opened tag from the stack
                if (!tagStack.isEmpty()) {
                    tagStack.pop();
                }
            } else {
                // Handle opening tag: calculate current depth (stack size + 1, since stack holds parent tags)
                int currentDepth = tagStack.size() + 1;
                // Extract the tag name (strip < and >)
                String tagName = tag.substring(1, tag.length() - 1);
                TagDepth currentTag = new TagDepth(tagName, currentDepth);
                
                // Push to stack (tracks current hierarchy)
                tagStack.push(currentTag);
                // Add to ArrayList (permanent record, like a Dictionary entry)
                tagDepthLog.add(currentTag);
                
                // Update max depth if needed
                if (currentDepth > maxNestingDepth) {
                    maxNestingDepth = currentDepth;
                }
            }
        }

        // Example 1: Print all tag-depth pairs (like iterating a Dictionary)
        System.out.println("Tag Nesting Depths:");
        for (TagDepth entry : tagDepthLog) {
            System.out.printf("%s: %d%n", entry.tagName, entry.depth);
        }

        // Example 2: Look up depth for a specific tag (like Dictionary.get())
        String targetTag = "span";
        for (TagDepth entry : tagDepthLog) {
            if (entry.tagName.equals(targetTag)) {
                System.out.printf("%nDepth of <%s>: %d%n", targetTag, entry.depth);
                break;
            }
        }

        // Example 3: Get overall max nesting depth
        System.out.printf("%nMaximum Nesting Depth: %d%n", maxNestingDepth);
    }
}

How This Mimics Dictionary Functionality #

• Storage: The ArrayList<TagDepth> stores every tag’s depth, just like a Dictionary stores key-value pairs.
• Lookup: To find a tag’s depth, you iterate the ArrayList (similar to checking a Dictionary’s keys) — if you need faster lookups, you could even use the ArrayList to build a temporary Map later, but since the goal is to use Stack and ArrayList, this works perfectly for learning purposes.
• Hierarchy Tracking: The Stack ensures we always know the current nesting level, which is critical for calculating the depth of each new tag.

This approach leverages the Stack’s strength at handling nested structures while using the ArrayList to maintain a queryable record of tag depths—exactly what you need for your assignment!

内容的提问来源于stack exchange，提问作者oliver