TIP102 Unit 3 Session 1 Standard (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
()
, []
, and {}
.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
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