STACK05 - Editorial

editorial
, ,
1

Problem Link - Valid Parenthesis

Problem Statement -

A string of parentheses is considered valid if each opening parenthesis has a matching closing parenthesis and the pairs are properly nested. In a valid parenthesis string, every opening bracket ( must have a corresponding closing bracket ) that occurs after the opening bracket, and there must not be any extra or unpaired brackets.

Approach:

The key idea behind this code is to use a stack to keep track of the parentheses as we traverse the expression.

  1. Stack for Parentheses:

    • We use an array a[] and a top variable to implement a stack where we push every opening parenthesis ( and pop it when a closing parenthesis ) is encountered.

    • The push() function adds an element to the stack, while pop() removes the top element.

  2. Checking Matching Pairs:

    • When a closing parenthesis ) is found, the program checks if there’s a corresponding opening parenthesis ( in the stack.

    • We use the isMatchingPair() function to ensure the popped character is an opening parenthesis that correctly matches the closing one.

  3. Balanced Expression:

    • As we go through the expression, if we encounter any mismatched or unpaired closing parenthesis, we immediately return false, meaning the expression is unbalanced.

    • After traversing the entire expression, if the stack is empty, it means every opening parenthesis was properly matched with a closing one, and the expression is balanced.

  4. Edge Case:

    • If we find a closing parenthesis but the stack is already empty (i.e., no matching opening parenthesis), the expression is unbalanced.

Time Complexity:

  • The time complexity is O(n), where n is the length of the expression. This is because we traverse the expression once, pushing and popping elements as we go.

Space Complexity:

  • The space complexity is O(n) in the worst case, where n is the number of characters in the expression, as we might need to store all opening parentheses in the stack.