Check for Balanced Parentheses in an Expression

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.

Example

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.

Code implementation

Let's implement the code:

#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.

Code implementation

#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 check balanced parentheses in an expression?

To check balanced parentheses, use a stack data structure. Iterate through the expression, push opening parentheses onto the stack, and pop for each closing parenthesis, ensuring the stack is empty at the end.

What is the balanced parentheses problem?

The balanced parentheses problem involves verifying if a given expression has matching open and close parentheses.

What are balanced parentheses in Java?

In Java, balanced parentheses are ensured using a stack. Iterate through the expression, push for opening parentheses, and pop for closing ones, ensuring the stack is empty at the end.

Which data structure is used to check for balanced parentheses?

A stack data structure is commonly used to check for balanced parentheses.

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.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, and many more!

Happy learning!