Check for Balanced Parentheses in an Expression

Introduction

Balanced parentheses mean that opening brackets and closing brackets maintain proper order logically. Checking for balanced parentheses is one of the popular problems asked in coding interviews. We will explain the approach for solving this problem as well as the intuition behind it.

What are Balanced Parentheses

Balanced parentheses is a sequence of parenthesis in which for every opening parenthesis, there is a corresponding closing parenthesis of the same type. Also the parenthesis sequence must be nested properly. For example {[{}]} is a balanced parenthesis whereas {[(])} is not a balanced parenthesis.

Problem statement

You are given a string expression of parentheses, containing the characters “(”, ”)”, ”{“, ”}”, “[“, “]”. The expression is balanced if

Open brackets are closed by the same type of closing brackets.
Open brackets must be closed in the correct order of their occurrence.

Check if the given expression is balanced or not.

Input

exp="{ ( ) [ ] }"

Output

the given expression is balanced

Explanation

For the given expression, open brackets are closed by the same type of closing brackets in proper order.

Note: Please try to solve the problem first and then see the below solution approach.

Approaches in Balanced Parentheses

There are a few approaches that can be used to solve the problem. One easier approach is a stack-based approach where space complexity is O(n) and time complexity is also O(n).

But here, in the desired approach, space complexity should be O(1). So, no extra space can be used.

Check for Balanced Bracket expression using Stack:

Let's take an example. Here we have the input string s with its output:

Input: s = "{()[]}"

Output: true

The approach is quite simple if we find an opening bracket("(,{,["), then we will simply store it in the stack. If we found a closing bracket, then first, we will check if our stack is empty or not; if it's empty, then we will simply return false since a closing bracket cannot come if there is no opening bracket. Also, if the stack is not empty, then we will check if the top element of our stack is matching to our closing bracket or not; if not, simply return false. At last, if everything is fine, return true.

Let's implement the code:

C++

#include <iostream>
#include <stack>

using namespace std;

bool isValid(string s) {
    stack<char> st;
    for (char ch : s) {
        if (ch == '(' || ch == '{' || ch == '[') {
            st.push(ch);
        } else {
            if (st.empty() || (st.top() != '(' && ch == ')') ||
                (st.top() != '{' && ch == '}' ) ||
                (st.top() != '[' && ch == ']')) {
                return false;
            }
            st.pop();
        }
    }
    return st.empty();
}

int main() {
    string s="{()[]}";

    if (isValid(s)) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }

    return 0;
}

Output:

true

Check for Balanced Bracket expression without using stack :

Let's take an example. Here we have the input string s with its output:

Input: s = "[()]{}{[()()]()}"

Output: true

The approach is we will use a variable "i" initialized with -1. Then we loop through a given string character by character. If we encounter an opening bracket, we increase the value of "i" by 1 and replace the "i-th" character of the string with the opening bracket. On the other hand, if we come across a closing bracket that matches the corresponding opening bracket stored at index "i", we decrease the value of "i" by 1.

If "i" is not -1 at the end, it means that there is at least one unbalanced bracket, so returns false or else true.

C++

#include <iostream>

using namespace std;

class Solution {
public:
    bool isValid(string s) {
        int i = -1;
        for (auto &ch : s) {
            if (ch == '(' || ch == '{' || ch == '[') {
                s[++i] = ch;
            } else {
                if (i >= 0 &&
                    ((s[i] == '(' && ch == ')') || (s[i] == '{' && ch == '}' ) ||
                    (s[i] == '[' && ch == ']'))) {
                    i--;
                } else {
                    return false;
                }
            }
        }
        return i == -1;
    }
};

int main() {
    string s="[()]{}{[()()]()}";

    if (Solution().isValid(s)) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }

    return 0;
}

Output:

true

Frequently Asked Questions

How do you know if parentheses are balanced?

A sequence of parenthesis is balanced if each opening bracket has a corresponding closing bracket of the same type. The parentheses string must also be nested properly in order to be a balanced string.

What are balanced parentheses in Java?

If the starting bracket appears to the left of the equivalent closing bracket, then the group of parentheses is said to be matched. Bracket pairs are not balanced if the brackets enclosing a string are not matched.

How do you solve balanced parentheses?

Balanced parentheses can be solved using stack. The goal is to stack all of the opening brackets. When you hit a closing bracket, look to see if the opening bracket of the same type is at the top of the stack. If this is true, then pop the stack and carry on with the iteration; if the stack is empty at the end, all of the brackets are correctly created. They are not balanced.

Conclusion

This article has covered the most optimized approach to check for balanced parentheses in an expression. You can also try to implement the stack-based approach, which is much easier as you are allowed to use an extra space there.

If you want to practice some such problems to get a good grasp on such concepts, then you can visit our Coding Ninjas Studio and also explore various topics like DSA, Web Technologies, Programming Fundamentals, Aptitude, and much more from our CN Library | Free Online Coding Resources.

Happy learning!