Check for balanced parenthesis without using stack
Given an expression string exp, write a program to examine whether the pairs and the orders of β{β, β}β, β(β, β)β, β[β, β]β are correct in exp.
Examples:
Input : exp = β[()]{}{[()()]()}β Output : true Input : exp = β[(])β Output : false
We have discussed a stack based solution. Here we are not allowed to use the stack. Looks like this problem cannot be solved without extra space (please see comments at the end). We use recursion to solve the problem.
Follow the steps below to solve the problem:
- Define a function findClosing(char c) which takes a character c representing an opening bracket and returns its corresponding closing bracket.
- Define a function check(char expr[], int n) which takes an array of characters expr representing the expression and its length n, and returns a boolean value indicating whether the expression is balanced or not.
- Implement the following logic inside the check() function:
- If n is 0, return true (empty expression is balanced).
- If n is 1, return false (single bracket is not balanced).
- If the first character in expr is a closing bracket, return false (unbalanced expression).
- Find the corresponding closing bracket for the first opening bracket in expr using the findClosing() function.
- Search for the closing bracket in the rest of the expression (expr[1] to expr[n-1]) and ensure that it appears after the opening bracket. If there are nested brackets, recursively check the sub-expression between the opening and closing brackets.
- If the closing bracket was not found or was in the wrong order, return false. Otherwise, remove the matched opening and closing brackets and recursively check the remaining expression.
- In the main function, call check() with the given expression and its length and print βBalancedβ or βNot Balancedβ based on the returned boolean value.
Below is the implementation of the above algorithm:
C++
// CPP program to check if parenthesis are // balanced or not in an expression. #include <bits/stdc++.h> using namespace std; char findClosing( char c) { if (c == '(' ) return ')' ; if (c == '{' ) return '}' ; if (c == '[' ) return ']' ; return -1; } // function to check if parenthesis are // balanced. bool check( char expr[], int n) { // Base cases if (n == 0) return true ; if (n == 1) return false ; if (expr[0] == ')' || expr[0] == '}' || expr[0] == ']' ) return false ; // Search for closing bracket for first // opening bracket. char closing = findClosing(expr[0]); // count is used to handle cases like // "((()))". We basically need to // consider matching closing bracket. int i, count = 0; for (i = 1; i < n; i++) { if (expr[i] == expr[0]) count++; if (expr[i] == closing) { if (count == 0) break ; count--; } } // If we did not find a closing // bracket if (i == n) return false ; // If closing bracket was next // to open if (i == 1) return check(expr + 2, n - 2); // If closing bracket was somewhere // in middle. return check(expr + 1, i - 1) && check(expr + i + 1, n - i - 1); } // Driver program to test above function int main() { char expr[] = "[(])" ; int n = strlen (expr); if (check(expr, n)) cout << "Balanced" ; else cout << "Not Balanced" ; return 0; } |
Java
// Java program to check if parenthesis are // balanced or not in an expression. import java.util.Arrays; class GFG { static char findClosing( char c) { if (c == '(' ) return ')' ; if (c == '{' ) return '}' ; if (c == '[' ) return ']' ; return Character.MIN_VALUE; } // function to check if parenthesis are // balanced. static boolean check( char expr[], int n) { // Base cases if (n == 0 ) return true ; if (n == 1 ) return false ; if (expr[ 0 ] == ')' || expr[ 0 ] == '}' || expr[ 0 ] == ']' ) return false ; // Search for closing bracket for first // opening bracket. char closing = findClosing(expr[ 0 ]); // count is used to handle cases like // "((()))". We basically need to // consider matching closing bracket. int i, count = 0 ; for (i = 1 ; i < n; i++) { if (expr[i] == expr[ 0 ]) count++; if (expr[i] == closing) { if (count == 0 ) break ; count--; } } // If we did not find a closing // bracket if (i == n) return false ; // If closing bracket was next // to open if (i == 1 ) return check(Arrays.copyOfRange(expr, i + 1 , n), n - 2 ); // If closing bracket was somewhere // in middle. // check in the middle part and check in the remaining part return check(Arrays.copyOfRange(expr, 1 , i), i - 1 ) && check(Arrays.copyOfRange(expr, (i + 1 ), n), n - i - 1 ); } // Driver code public static void main(String[] args) { char expr[] = "[(])" .toCharArray(); int n = expr.length; if (check(expr, n)) System.out.println( "Balanced" ); else System.out.println( "Not Balanced" ); } } /* This code contributed by PrinciRaj1992 */ |
Python3
def findClosing(c): if (c = = '(' ): return ')' if (c = = '{' ): return '}' if (c = = '[' ): return ']' return None def check(expr): n = len (expr) # Base cases if (n = = 0 ): return True if (n = = 1 ): return False if (expr[ 0 ] = = ')' or expr[ 0 ] = = '}' or expr[ 0 ] = = ']' ): return False # Search for closing bracket for first # opening bracket. closing = findClosing(expr[ 0 ]) # count is used to handle cases like # "((()))". We basically need to # consider matching closing bracket. i, count = 1 , 0 while i < n: if (expr[i] = = expr[ 0 ]): count + = 1 if (expr[i] = = closing): if (count = = 0 ): break count - = 1 i + = 1 # If we did not find a closing # bracket if (i = = n): return False # If closing bracket was next # to open if (i = = 2 ): return check(expr[i:n - 1 ]) # If closing bracket was somewhere # in middle. return check(expr[ 1 :i]) and check(expr[i + 1 :n]) # Driver code if __name__ = = '__main__' : expr = "[(])" if (check(expr)): print ( "Balanced" ) else : print ( "Not Balanced" ) |
C#
// C# program to check // if parenthesis are // balanced or not in // an expression. using System; class GFG{ static char [] copyOfRange ( char [] src, int start, int end) { int len = end - start; char [] dest = new char [len]; Array.Copy(src, start, dest, 0, len); return dest; } static char findClosing( char c) { if (c == '(' ) return ')' ; if (c == '{' ) return '}' ; if (c == '[' ) return ']' ; return char .MinValue; } // Function to check if // parenthesis are balanced. static bool check( char []expr, int n) { // Base cases if (n == 0) return true ; if (n == 1) return false ; if (expr[0] == ')' || expr[0] == '}' || expr[0] == ']' ) return false ; // Search for closing bracket for first // opening bracket. char closing = findClosing(expr[0]); // count is used to handle cases like // "((()))". We basically need to // consider matching closing bracket. int i, count = 0; for (i = 1; i < n; i++) { if (expr[i] == expr[0]) count++; if (expr[i] == closing) { if (count == 0) break ; count--; } } // If we did not find // a closing bracket if (i == n) return false ; // If closing bracket // was next to open if (i == 1) return check(copyOfRange(expr, i + 1, n), n - 2); // If closing bracket // was somewhere in middle. return check(copyOfRange(expr, 1, n), i - 1) && check(copyOfRange(expr, (i + 1), n), n - i - 1); } // Driver code public static void Main(String[] args) { char []expr = "[(])" .ToCharArray(); int n = expr.Length; if (check(expr, n)) Console.WriteLine( "Balanced" ); else Console.WriteLine( "Not Balanced" ); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // Javascript program to check if parenthesis are // balanced or not in an expression. function findClosing(c) { if (c == '(' ) return ')' ; if (c == '{' ) return '}' ; if (c == '[' ) return ']' ; return -1; } // function to check if parenthesis are // balanced. function check(expr, n) { // Base cases if (n == 0) return true ; if (n == 1) return false ; if (expr[0] == ')' || expr[0] == '}' || expr[0] == ']' ) return false ; // Search for closing bracket for first // opening bracket. var closing = findClosing(expr[0]); // count is used to handle cases like // "((()))". We basically need to // consider matching closing bracket. var i, count = 0; for (i = 1; i < n; i++) { if (expr[i] == expr[0]) count++; if (expr[i] == closing) { if (count == 0) break ; count--; } } // If we did not find a closing // bracket if (i == n) return false ; // If closing bracket was next // to open if (i == 1) return check(expr + 2, n - 2); // If closing bracket was somewhere // in middle. return check(expr + 1, i - 1) && check(expr + i + 1, n - i - 1); } // Driver program to test above function var expr = "[(])" ; var n = expr.length; if (check(expr, n)) document.write( "Balanced" ); else document.write( "Not Balanced" ); // This code is contributed by itsok. </script> |
Not Balanced
Time Complexity:
The given implementation of the balanced parenthesis check algorithm uses recursion. For each recursive call, we iterate over the input expression once. Thus, the time complexity can be expressed as O(n^2), where n is the length of the input expression.
Space Complexity:
The algorithm uses recursion, which creates a new stack frame for each recursive call. The space occupied by the stack frames is proportional to the maximum depth of the recursion tree. The maximum depth of the recursion tree in the worst case is n/2, where n is the length of the input expression. Therefore, the space complexity of the algorithm can be expressed as O(n).
The above solution is very inefficient compared to the stack-based solution. This seems to only useful for recursion practice problems.