Balanced Parentheses

Pseudo Code of Balanced Parentheses

• Declare a character stack.
• Now traverse the expression string

       1-  If the current character is an opening bracket ( ‘(‘ or ‘{‘ or ‘[‘ ) then push it to 

     stack.

       2-  If the current character is a closing bracket ( ‘)’ or ‘}’ or ‘]’ ) then pop from 

     stack and if the popped character is the matching opening bracket, then fine 

     else parenthesis are not balanced.

• After complete traversal, if there is some opening bracket left in the stack, then “not balanced”.
• Otherwise, the string is balanced.

Below C++ code is given for your better understanding:

// CPP program to check for balanced parentheses. #include <bits/stdc++.h> using namespace std; bool isValidParentheses(string expression) {       // Make an inbuilt stack.     stack<char> s;     char x;       // Traversing the Expression.     for (int i = 0; i < expression.length(); i++)      {         if (expression[i] == '(' || expression[i] == '[' || expression[i] == '{')          {             // Push the element in the stack.             s.push(expression[i]);             continue;         }           /*             If current current character is not opening             bracket, then it must be closing. So stack             cannot be empty at this point.         */         if (s.empty())         {             return false;         }           // Store the top element.         x = s.top();         s.pop();                 // Check for opening braces in the stack of corresponding closing braces.         switch (expression[i]) {         case ')':                         if (x == '{' || x == '[')             {                 return false;             }             break;           case '}':               if (x == '(' || x == '[')             {                 return false;             }             break;           case ']':                         if (x == '(' || x == '{')             {                 return false;             }             break;         }     }       // Check Empty Stack.     return (s.empty()); } // Driver code int main() {     string expr = "{{()]}";     // Function call     if (isValidParentheses(expr))         cout << "Balanced";     else         cout << "Not Balanced";     return 0; }

Output for the above code with input string “{{()]}” is as follows:

Not Balanced

Complexity Analysis of Balanced Parentheses

Time Complexity

O(N), Where N is the length of the string. 

Reason: As the traversal of the string or expression is done only once.

Space Complexity

O(N), Where N is the length of the string.

Reason: As the maximum stack size reaches the length of the string.

Let’s go through the visualisation below for a quick recap:

See More, floyd's algorithm

Also See, binary search algorithm

Frequently Asked Questions

What is a stack?

A stack is an abstract data type that serves as a collection of elements and has two primary operations: Push, which adds an element to the collection, and Pop, which removes the most recently added element that has not yet been removed.

What data structure can be used to check if the syntax has balanced parentheses?

Stack comes in handy to check if the syntax has balanced parentheses.

What is balanced parentheses?

A string of parentheses is intuitively balanced if each left parenthesis has a matching right parenthesis and the matched pairs are well nested.

What is stack pop ()?

Stack pop() removes the most recently added element that has not yet been removed.

Where can I practice more stack problems?

You can use CodeStudio to practise a wide range of DSA questions typically asked in interviews at big MNCs.

Conclusion

This article discusses the problem Balanced Parentheses, as well as some essential hints to assist you in coming up with a solution.

The stack data structure comes in handy here to determine whether or not the syntax has balanced parentheses.

It is rigorous practicing which helps us to hone our skills. You can find a wide variety of practice problems, specifically dynamic programming to practically utilise the knowledge you gained here.

Apart from this, you can use CodeStudio to practice a wide range of DSA questions typically asked in interviews at big MNCs. This will assist you in mastering efficient coding techniques and provide you with interview experiences from scholars in large product-based organisations.