Post Format Validator - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 1 Standard (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What are the valid types of tags?
  • A: The valid tags are (), [], and {}.
• Q: What should be done if an opening tag does not have a matching closing tag?
  • A: The post is considered invalid.
• Q: How should the order of tags be handled?
  • A: Tags must be closed in the correct order, meaning that the most recently opened tag must be the first one closed.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to track opening tags and ensure they match with closing tags in the correct order.

1. Initialize a stack to keep track of the opening tags as you encounter them.
2. Iterate through the post's characters:
   1. If it's an opening tag (`(`, `[`, `{`), push it onto the stack.
   2. If it's a closing tag (`)`, `]`, `}`), check the following:
      1. If the stack is empty, return `False` (no matching opening tag).
      2. If the tag at the top of the stack is not the corresponding opening tag, return `False`.
      3. If it matches, pop the opening tag from the stack (this pair is correctly nested).
   3. Continue until all characters are processed.
3. After processing all characters, check the stack:
   1. If the stack is empty, all tags were properly nested; return `True`.
   2. If the stack is not empty, some opening tags were not closed; return `False`.

⚠️ Common Mistakes

• Forgetting to check if the stack is empty before trying to pop.
• Not ensuring that tags are closed in the correct order.
• Confusing the different types of tags and their corresponding pairs.

I-mplement

def is_valid_post_format(post):
  stack = []
  matching_tags = {')': '(', ']': '[', '}': '{'}

  for char in post:
    if char in '([{':
      stack.append(char)
    elif char in ')]}':
      if not stack or stack.pop() != matching_tags[char]:
        return False

  return len(stack) == 0