Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What are Balanced Parentheses?
3.
Problem statement
4.
Example
4.1.
Input
4.2.
Output
4.3.
Explanation
5.
Approaches in Balanced Parentheses
5.1.
Check for Balanced Bracket expression using Stack:
5.2.
C++
5.3.
Output:
5.4.
Check for Balanced Bracket expression without using stack :
5.5.
C++
5.6.
Output:
6.
Frequently Asked Questions
6.1.
How do you check balanced parentheses in an expression?
6.2.
What is the balanced parentheses problem?
6.3.
What are balanced parentheses in Java?
6.4.
Which data structure is used to check for balanced parentheses?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check for Balanced Parentheses in an Expression

Author Malay Gain
2 upvotes

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.

balanced parentheses

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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:

  • C++

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.

Code implementation

  • C++

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 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 AlgorithmsCompetitive Programming, and many more!

Happy learning!

Live masterclass