enjoyalgorithms

Check for Balanced Parentheses in an Expression

Difficulty: Medium, Asked-In: Amazon, Adobe, Hike

Key takeaway: An excellent problem to learn problem solving using the stack data structure.

Let’s understand the problem

Given an expression string containing opening and closing parentheses, write a program to check if the expression is a balanced expression or not. An expression is balanced if each opening parenthesis is closed by the same type of closing parenthesis in the exact same order.

Examples

Input: exp[] = "[ ( ) ] { } { ( ) ( ) }", Output: Balanced

Explanation: The expression is balanced because all the parentheses are well-formed.

Input: exp[] = "[ ( ] )" Output: Not Balanced

Explanation: The expression is not balanced because there is a closing parenthesis ']' after the opening parenthesis '('.

Solution approach using stack

Solution idea

If we observe the order of parentheses in a correct expression, we can visualize a Last-In-First-Out (LIFO) structure: the opening parenthesis that comes last will have the corresponding closing parenthesis come first in the expression. So, we can use stack to validate the correct order of parentheses in the expression.

The idea is to use a stack to keep track of opening parentheses. In other words, when we encounter an opening parenthesis, we push it into the stack. If we encounter a closing parenthesis, we check if the top element of the stack is the corresponding opening parenthesis. If the stack is empty or the parentheses don't match, the expression is not balanced. Finally, after processing all the elements, if the stack is empty, then the expression is balanced; otherwise, it is not.

Check for balanced parentheses in an expression solution visualization using stack

Solution steps

  1. First, we check if the length of the expression is odd. If it is, there cannot be a matching closing parenthesis for each opening parenthesis, so the expression is unbalanced.
  2. Now, we create an empty stack s to store the opening symbols.
  3. We iterate through the expression using a loop. For each character exp[i], if it is an opening symbol '(', '{', or '[', we push it onto the stack. If exp[i] is a closing symbol ')', '}', or ']', we need to check if there is a matching opening symbol at the top of the stack.
  4. If the stack is not empty, we pop the top element from the stack and compare it with the current closing symbol. If they do not form a correct pair, we return false. If the stack is empty, it means there is no corresponding opening symbol for the current closing symbol, so we return false.
  5. After iterating through all the characters in the expression, if the stack is empty, it means all the opening symbols have been properly closed by their corresponding closing symbols, and the expression is balanced. If the stack is not empty, it means there are unmatched opening symbols, and the expression is unbalanced.

Solution code C++

bool checkValidParentheses(string& exp, int n) 
{
    if (n % 2 != 0)
        return false;

    stack<char> s;
    for (int i = 0; i < n; i = i + 1) 
    {
        if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
            s.push(exp[i]);

        else if (exp[i] == ')' || exp[i] == '}' || exp[i] == ']') 
        {
            if (s.empty())
                return false;
          
            char top = s.top();
            s.pop();
            if ((top == '(' && exp[i] != ')') ||
                (top == '{' && exp[i] != '}') ||
                (top == '[' && exp[i] != ']'))
                return false;
        }
    }

    return s.empty();
}

Another implementation using switch statement

bool checkValidParentheses(string& exp) 
{
    stack<char> s;
    char temp;

    for (char ch : exp) 
    {
        if (ch == '(' || ch == '[' || ch == '{') 
        {
            s.push(ch);
            continue;
        }

        if (s.empty())
            return false;

        temp = s.top();
        s.pop();

        switch (ch) 
        {
            case ')':
                if (temp == '{' || temp == '[')
                    return false;
                break;
            case '}':
                if (temp == '(' || temp == '[')
                    return false;
                break;
            case ']':
                if (temp == '(' || temp == '{')
                    return false;
                break;
        }
    }

    return s.empty();
}

Time and space complexity analysis

We are running a single loop and performing constant operations at each iteration. So the time complexity is n * O(1) = O(n). From another perspective, we will be inserting and removing each opening parenthesis once from the stack in the worst case. This situation occurs when the expression is completely balanced. So, the total number of stack operations is n.

We are using extra space for the stack. The size of the stack will be O(n) in the worst case, so the space complexity is O(n).

Another solution approach using stack

Solution idea

In this approach, for each character exp[i], we check if it is an opening parenthesis. If it is, we push the corresponding closing parenthesis onto the stack. For example, if exp[i] is "(", then we push ")" onto the stack. This helps us keep track of the expected closing parentheses.

If exp[i] is not an opening parenthesis, then it must be a closing parenthesis. We check if the stack is not empty and if the top element of the stack is exp[i]. If they match, it means the current closing parenthesis matches the expected closing parenthesis. In such cases, we remove the top element from the stack.

If any of the above conditions is not satisfied, it means the expression is unbalanced. So, we return false.

Solution code C++

bool checkValidParentheses(string& exp) 
{
    int n = exp.length();

    if (n % 2 != 0)
        return false;

    stack<char> s;
    for (int i = 0; i < n; i = i + 1) 
    {
        if (exp[i] == '(')
            s.push(')');
        else if (exp[i] == '{')
            s.push('}');
        else if (exp[i] == '[')
            s.push(']');
        else if (!s.empty() && s.top() == exp[i])
            s.pop();
        else
            return false;
    }

    return s.empty();
}

Time and space complexity analysis

We are running a single loop n times and performing constant operations at each iteration. So, the time complexity is n * O(1) = O(n).

The worst case occurs when the expression is completely balanced, and we will traverse the entire string. In this situation, we insert and remove each closing parenthesis only once. So, the total number of stack operations in the worst case = The total number of closing parentheses in a balanced expression = n/2.

We are using extra space for the stack. So, the space complexity is O(n).

Another approach without using library stack

Solution idea

This approach is similar to the stack approach, but for validating the balance of parentheses in the expression, we scan the expression from left to right and use the starting indexes of the same input array as a stack to store the opening parentheses. During this process, we also maintain a count variable to keep track of the number of opening parentheses encountered.

The idea is simple: A balanced expression should have an equal number of opening and closing parentheses, and they should be properly nested and matched. So, the expression is balanced if and only if the count becomes -1 at the end of the loop.

Solution steps

Step 1: We initialize a count variable to track the count of opening parentheses. Now we iterate from 0 to n-1 using a loop.

Step 2: If the current character exp[i] is an opening parenthesis.

We increment the count and store the opening parenthesis in the count-th position of the exp string. This is similar to pushing the opening parenthesis onto the stack.

Step 3: If the current character is a closing parenthesis.

If the count is -1, it means there is no corresponding opening parenthesis for the current closing parenthesis. So the expression is unbalanced and we return false.

If the count is not -1, we retrieve the opening parenthesis from the top of the stack (stored at exp[count]) and compare it with the current closing parenthesis exp[i].

  • If they do not match, then the expression is unbalanced, and we return false. 
  • If they match, we decrement the count variable by 1 to simulate popping the opening parenthesis.

Step 4: After the loop, we check if the count is -1. If it is, then all opening parentheses have been matched and popped from the stack. So the expression is balanced and we return true. Otherwise, there are unmatched opening parentheses remaining. So the expression is unbalanced, and we return false.

Solution code C++

bool checkValidParentheses(string& exp) 
{
    int n = exp.length();
    int count = -1;
    for (int i = 0; i < n; i = i + 1) 
    {
        if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[') 
        {
            count = count + 1;
            exp[count] = exp[i];
        } 
        else if (exp[i] == ')' || exp[i] == '}' || exp[i] == ']') 
        {
            if (count == -1)
                return false;

            char openingParenthesis = exp[count];
            if ((openingParenthesis == '(' && exp[i] != ')') ||
                (openingParenthesis == '{' && exp[i] != '}') ||
                (openingParenthesis == '[' && exp[i] != ']')) 
            {
                return false;
            }

            count = count - 1;
        }
    }

    return (count == -1);
}

Note: Strings in Python are immutable i.e. we cannot change individual characters of a string directly. If we try to modify a string in place, it will throw an error in Python. In other words, this assignment operation exp[count] = exp[i] attempts to assign a new value to a character in the exp string. This is not allowed in Python. To fix this issue, we can create a new string or list to store the modified expression.

Time and space complexity analysis

We are running a single loop n times and performing constant operations at each iteration. So the time complexity is n * O(1) = O(n). We are modifying the same input array as a stack to store opening parentheses. So the space complexity is O(1).

Special case 1: if there are only ( and ) parentheses

The simple idea is to iterate over the string of parentheses and keep track of the count of opening parentheses encountered. For each closing parenthesis, we decrement the count to match it with the corresponding opening parenthesis. If the count becomes negative at any point or if there are unmatched opening parentheses remaining at the end, the expression is unbalanced. Otherwise, the expression is balanced.

We initialize a boolean variable balanceFlag as true to keep track of the balanced status of the expression. We also initialize a variable count to keep track of the number of opening parentheses encountered.

bool checkValidParentheses(string& exp, int n) 
{
    bool balanceFlag = true;
    int count = 0;

    for (int i = 0; i < n; i = i + 1) 
    {
        if (exp[i] == '(')
            count = count + 1;
        else
            count = count - 1;
        if (count < 0) 
        {
            balanceFlag = false;
            break;
        }
    }

    if (count != 0)
        balanceFlag = false;

    return balanceFlag;
}

Critical ideas to think!

  • Is this idea correct? We can take three variables to count every three braces. If we encounter an open brace, we increment the corresponding variable and decrement it when we see a closing brace. Whenever any variable gets a value < 0, we return false; otherwise, true.
  • Can we think of solving this problem using recursion?
  • Can we think of solving this using a hash table?
  • Can we solve this problem using some other approach?

Similar coding questions to explore

  • Given a string containing only parentheses, find the length of the longest valid parentheses.
  • Given a string containing parentheses, remove the minimum number of invalid parentheses to make the input string valid.
  • Given an integer n, generate all combinations of well-formed parentheses of length 2n. For example, given n = 3, the function should return [“((()))”, “(()())”, “(())()”, “()(())”, “()()()”].
  • Given a string of parentheses, return the minimum number of parentheses that need to be added to make the input string valid.
  • Given a string containing parentheses, count the number of valid (well-formed) parentheses substrings.

If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!

More from EnjoyAlgorithms

Self-paced Courses and Blogs