Balanced Parentheses Problem Using Stack in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using a stack to check for balanced parentheses?

Use a stack to keep track of opening parentheses. For every closing parenthesis, check if it matches the top of the stack. If all match and stack is empty at the end, parentheses are balanced.

beginner

Which characters are pushed onto the stack in the balanced parentheses problem?

Only opening parentheses like '(', '{', and '[' are pushed onto the stack.

beginner

What should happen when a closing parenthesis is encountered during the check?

Pop the top element from the stack and check if it matches the type of closing parenthesis. If it doesn't match or stack is empty, parentheses are not balanced.

beginner

Why must the stack be empty at the end of the parentheses check?

If the stack is not empty, it means there are unmatched opening parentheses left, so the parentheses are not balanced.

intermediate

What is the time complexity of checking balanced parentheses using a stack?

The time complexity is O(n), where n is the length of the string, because each character is processed once.

What data structure is best suited for checking balanced parentheses?

A Queue

B Stack

C Array

D Linked List

Stack follows Last-In-First-Out, which matches the nested structure of parentheses.

What should you do when you encounter an opening parenthesis in the string?

A Replace it with closing parenthesis

B Pop from the stack

C Ignore it

D Push it onto the stack

Opening parentheses are pushed onto the stack to be matched later.

If the stack is empty when a closing parenthesis is found, what does it mean?

A There is no matching opening parenthesis

B Stack overflow

C Parentheses are balanced

D Ignore the closing parenthesis

A closing parenthesis without a matching opening one means unbalanced parentheses.

Which of these strings is balanced?

A ({[]})

B ({[)]}

C ((())

D (()))

Only '({[]})' has matching pairs in correct order.

What is the final check after processing all characters in the string?

A Stack size should be odd

B Stack should have one element

C Stack should be empty

D Stack size should be even

An empty stack means all opening parentheses were matched.

Explain step-by-step how a stack is used to check if parentheses in a string are balanced.

Think about how you track opening brackets and match them with closing ones.

Describe what conditions cause the parentheses to be considered unbalanced when using a stack.

Consider what happens if you find a closing bracket but no matching opening bracket.