Given a string of balanced expressions, find if it contains a redundant parenthesis or not. A set of parenthesis is redundant if the same sub-expression is surrounded by unnecessary or multiple brackets. Print ‘Yes’ if redundant else ‘No’.
Note: Expression may contain ‘+’, ‘*‘, ‘–‘ and ‘/‘ operators. Given expression is valid and there are no white spaces present.
Note: The problem is intended to solve in O(1) extra space.
Examples:
Input: ((a+b))
Output: YES
((a+b)) can reduced to (a+b)
Input: (a+(b)/c)
Output: YES
(a+(b)/c) can reduced to (a+b/c) because b is surrounded by () which is redundant
Input: (a+b*(c-d))
Output: NO
(a+b*(c-d)) doesn’t have any redundant or multiple brackets
Approach:
The idea is very similar to the idea discussed in the previous article but here in place of stack we are counting the symbol ( ‘+’, ‘*‘, ‘–‘ and ‘/‘ ) and the total number of brackets used in the expression.
If the count of brackets is not equal to the count of the symbols then the function will return false.
C++
// C++ program to check for/// redundant braces in the string#include <iostream>using namespace std;// Function to check for// redundant bracesbool IsRedundantBraces(string A){ // count of no of signs int a = 0, b = 0; for (int i = 0; i < A.size(); i++) { if (i + 2 < A.size() && A[i] == '(' && A[i + 2] == ')') return 1; if (A[i] == '*' || A[i] == '+' || A[i] == '-' || A[i] == '/') a++; if (A[i] == '(') b++; } if (b > a) return 1; return 0;}// Driver functionint main(){ string A = "(((a+b) + c) + d)"; if (IsRedundantBraces(A)) { cout << "YES\n"; } else { cout << "NO"; }} |
Java
// Java program to check for// redundant braces in the string class GFG { // Function to check for // redundant braces static boolean IsRedundantBraces(String A) { // count of no of signs int a = 0, b = 0; for (int i = 0; i < A.length(); i++) { if (A.charAt(i) == '(' && A.charAt(i + 2) == ')') return true; if (A.charAt(i) == '*' || A.charAt(i) == '+' || A.charAt(i) == '-' || A.charAt(i) == '/') a++; if (A.charAt(i) == '(') b++; } if (b > a) return true; return false; } // Driver Code public static void main (String[] args) { String A = "(((a+b) + c) + d)"; if (IsRedundantBraces(A)) { System.out.println("YES"); } else { System.out.println("NO"); } } }// This code is contributed by AnkitRai01 |
Python3
# Python3 program to check for/# redundant braces in the string# Function to check for# redundant bracesdef IsRedundantBraces(A): # count of no of signs a, b = 0, 0; for i in range(len(A)): if (A[i] == '(' and A[i + 2] == ')'): return True; if (A[i] == '*' or A[i] == '+' or A[i] == '-' or A[i] == '/'): a += 1; if (A[i] == '('): b += 1; if (b > a): return True; return False;# Driver Codeif __name__ == '__main__': A = "(((a+b) + c) + d)"; if (IsRedundantBraces(A)): print("YES"); else: print("NO"); # This code is contributed by PrinciRaj1992 |
C#
// C# program to check for// redundant braces in the string using System; class GFG { // Function to check for // redundant braces static bool IsRedundantBraces(string A){ // count of no of signs int a = 0, b = 0; for (int i = 0; i < A.Length; i++) { if (A[i] == '(' && A[i + 2] == ')') return true; if (A[i] == '*' || A[i] == '+' || A[i] == '-' || A[i] == '/') a++; if (A[i] == '(') b++; } if (b > a) return true; return false;} // Driver Codepublic static void Main (String[] args){ String A = "(((a+b) + c) + d)"; if (IsRedundantBraces(A)) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } } }// This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program to check for // redundant braces in the string // Function to check for // redundant braces function IsRedundantBraces(A) { // count of no of signs let a = 0, b = 0; for (let i = 0; i < A.length; i++) { if (A[i] == '(' && A[i + 2] == ')') return true; if (A[i] == '*' || A[i] == '+' || A[i] == '-' || A[i] == '/') a++; if (A[i] == '(') b++; } if (b > a) return true; return false; } let A = "(((a+b) + c) + d)"; if (IsRedundantBraces(A)) { document.write("YES"); } else { document.write("NO"); } // This code is contributed by divyeshrabadiya07.</script> |
NO
Time Complexity: O(n), where n is the length of the given string.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
