Given a valid expression Exp containing only binary operators ‘+‘, ‘–‘, ‘*‘, ‘/‘, and operands, remove all the redundant parenthesis. A set of parenthesis is said to be redundant if, removing them, does not change the value of the expression.
Note: The operators ‘+’ and ‘-‘ have the same priority. ‘*’ and ‘/’ also have the same priority. ‘*’ and ‘/’ have more priority than ‘+’ and ‘-‘.
Example:
Input: Exp = (A*(B+C))
Output: A*(B+C)
Explanation: The outermost parenthesis are redundant.Input: Exp = A+(B+(C))
Output: A+B+C
Explanation: All the parenthesis are redundant.
Approach: This can be solved with the following idea:
The goal is to discover which brackets from an expression can be safely eliminated by combining stack-based parsing with operator precedence rules. A further array can be used to keep track of whether each character in the input string is a redundant bracket in addition to three arrays to track the Previous and Next operators for each location.
Below are the steps involved in the implementation of the code:
- We need to first convert the input expression string “Exp” to a character array “s” and find the length of the array “n“.
- It first initializes an array ans with all 1s of length n + 1, where n is the length of the expression.
- Create two integer arrays, lasta, and nxta, with length n + 1, to store the last and next operators encountered before and after each index.
- Initialize a stack, an array sign of length 256 with -1, and an array mp of length 256 with 0. These arrays keep track of the last occurrence of an operator and whether an operator is present in the current sub-expression inside parentheses.
- Loop through the character array, updating the sign and mp arrays if the character is an operator.
- If the character is ‘(‘, push its index onto the stack. If it is ‘)’, pop the index of the corresponding opening parenthesis from the stack.
- If the character is ‘)’, check if the current set of parentheses is required by looking at the last and next operator indices of the opening and closing parentheses.
- Handle corner cases, such as the first and last characters being parentheses, and cases where no operands are present inside the parentheses.
- Update the array of ones to store whether each character is inside redundant parentheses or not.
- Construct a new string by appending all characters in the expression that are not inside redundant parentheses.
- Return the new string.
Below is the code implementation of the above approach:
C++
// C++ code of the above approach#include <bits/stdc++.h>using namespace std;// Function to remove redundant bracketsstring removeBrackets(string Exp){ char s[Exp.length() + 1]; strcpy(s, Exp.c_str()); int n = strlen(s); int ans[n + 1]; memset(ans, 1, sizeof(ans)); int lasta[n + 1]; int nxta[n + 1]; int l = -1; // Start Iterating from // starting index for (int i = 0; i < n; i++) { lasta[i] = l; if (s[i] == '*' || s[i] == '+' || s[i] == '-' || s[i] == '/') l = s[i]; } // Start Iterating from // last index l = -1; for (int i = n - 1; i >= 0; i--) { nxta[i] = l; if (s[i] == '*' || s[i] == '+' || s[i] == '-' || s[i] == '/') l = s[i]; } stack<int> st; int sign[256]; int mp[256]; memset(sign, -1, sizeof(sign)); char operand[] = { '*', '+', '-', '/' }; for (int p = 0; p < n; p++) { for (char x : operand) { mp[x] = 0; if (x == s[p]) sign[x] = p; } if (s[p] == '(') st.push(p); else if (s[p] == ')') { int i = st.top(); st.pop(); int j = p; int nxt = nxta[j]; int last = lasta[i]; // Iterate in operator // array for (char x : operand) { if (sign[x] >= i) { mp[x] = 1; } } int ok = 0; if (i > 0 && j + 1 < n && s[i - 1] == '(' && s[j + 1] == ')') ok = 1; if (mp['+'] == 0 && mp['*'] == 0 && mp['-'] == 0 && mp['/'] == 0) ok = 1; if (last == -1 && nxt == -1) ok = 1; if (last == '/') { } else if (last == '-' && (mp['+'] == 1 || mp['-'] == 1)) { } else if (mp['-'] == 0 && mp['+'] == 0) { ok = 1; } else { if ((last == -1 || last == '+' || last == '-') && (nxt == -1 || nxt == '+' || nxt == '-')) ok = 1; } // If the pair is redundant if (ok == 1) { ans[i] = 0; ans[j] = 0; } } } // Final string string res = ""; for (int i = 0; i < n; i++) { if (ans[i] > 0) { res += s[i]; } } return res;}// Driver codeint main(){ string expression = "(A*(B+C))"; // Function call string result = removeBrackets(expression); cout << result << endl; return 0;}// This code is contributed by prasad264 |
Java
// Java code of the above approachimport java.util.*;class Solution { // Function to redundant brackets public static String removeBrackets(String Exp) { // Code here char[] s = Exp.toCharArray(); int n = Exp.length(); int ans[] = new int[n + 1]; Arrays.fill(ans, 1); int lasta[] = new int[n + 1]; int nxta[] = new int[n + 1]; int l = -1; // Start Iterating from // starting index for (int i = 0; i < n; i++) { lasta[i] = l; if (s[i] == '*' || s[i] == '+' || s[i] == '-' || s[i] == '/') l = s[i]; } // Start Iterating from // last index l = -1; for (int i = n - 1; i >= 0; i--) { nxta[i] = l; if (s[i] == '*' || s[i] == '+' || s[i] == '-' || s[i] == '/') l = s[i]; } Stack<Integer> st = new Stack<>(); int sign[] = new int[256]; int mp[] = new int[256]; Arrays.fill(sign, -1); char[] operand = { '*', '+', '-', '/' }; for (int p = 0; p < n; p++) { for (char x : operand) { mp[x] = 0; if (x == s[p]) sign[x] = p; } if (s[p] == '(') st.push(p); else if (s[p] == ')') { int i = st.pop(); int j = p; int nxt = nxta[j]; int last = lasta[i]; // Iterate in operator // array for (char x : operand) { if (sign[x] >= i) { mp[x] = 1; } } int ok = 0; if (i > 0 && j + 1 < n && s[i - 1] == '(' && s[j + 1] == ')') ok = 1; if (mp['+'] == 0 && mp['*'] == 0 && mp['-'] == 0 && mp['/'] == 0) ok = 1; if (last == -1 && nxt == -1) ok = 1; if (last == '/') { } else if (last == '-' && (mp['+'] == 1 || mp['-'] == 1)) { } else if (mp['-'] == 0 && mp['+'] == 0) { ok = 1; } else { if ((last == -1 || last == '+' || last == '-') && (nxt == -1 || nxt == '+' || nxt == '-')) ok = 1; } // If the pair is reduntant if (ok == 1) { ans[i] = 0; ans[j] = 0; } } } // Final string StringBuffer res = new StringBuffer(); for (int i = 0; i < n; i++) { if (ans[i] > 0) { res.append(s[i]); } } return res.toString(); } // Driver code public static void main(String[] args) { String expression = "(A*(B+C))"; // Function call String result = removeBrackets(expression); System.out.println(result); }} |
Python3
class Solution: # Function to redundant brackets @staticmethod def removeBrackets(Exp): # Code here s = list(Exp) n = len(Exp) ans = [1]*(n+1) lasta = [0]*(n+1) nxta = [0]*(n+1) l = -1 # Start Iterating from # starting index for i in range(n): lasta[i] = l if s[i] == '*' or s[i] == '+' or s[i] == '-' or s[i] == '/': l = s[i] # Start Iterating from # last index l = -1 for i in range(n - 1, -1, -1): nxta[i] = l if s[i] == '*' or s[i] == '+' or s[i] == '-' or s[i] == '/': l = s[i] st = [] sign = [-1]*256 mp = [0]*256 operand = ['*', '+', '-', '/'] for p in range(n): for x in operand: mp[ord(x)] = 0 if x == s[p]: sign[ord(x)] = p if s[p] == '(': st.append(p) elif s[p] == ')': i = st.pop() j = p nxt = nxta[j] last = lasta[i] # Iterate in operator # array for x in operand: if sign[ord(x)] >= i: mp[ord(x)] = 1 ok = 0 if i > 0 and j + 1 < n and s[i - 1] == '(' and s[j + 1] == ')': ok = 1 if mp[ord('+')] == 0 and mp[ord('*')] == 0 and mp[ord('-')] == 0 and mp[ord('/')] == 0: ok = 1 if last == -1 and nxt == -1: ok = 1 if last == '/': pass elif last == '-' and (mp[ord('+')] == 1 or mp[ord('-')] == 1): pass elif mp[ord('-')] == 0 and mp[ord('+')] == 0: ok = 1 else: if (last == -1 or last == '+' or last == '-') and (nxt == -1 or nxt == '+' or nxt == '-'): ok = 1 # If the pair is reduntant if ok == 1: ans[i] = 0 ans[j] = 0 # Final string res = "" for i in range(n): if ans[i] > 0: res += s[i] return res# Driver codeif __name__ == '__main__': expression = "(A*(B+C))" # Function call result = Solution.removeBrackets(expression) print(result) |
C#
// C# code of the above approachusing System;using System.Collections.Generic;using System.Text;class Solution{ // Function to remove redundant brackets public static string removeBrackets(string Exp) { char[] s = Exp.ToCharArray(); int n = Exp.Length; int[] ans = new int[n + 1]; Array.Fill(ans, 1); int[] lasta = new int[n + 1]; int[] nxta = new int[n + 1]; int l = -1; // Start Iterating from starting index for (int i = 0; i < n; i++) { lasta[i] = l; if (s[i] == '*' || s[i] == '+' || s[i] == '-' || s[i] == '/') l = s[i]; } // Start Iterating from last index l = -1; for (int i = n - 1; i >= 0; i--) { nxta[i] = l; if (s[i] == '*' || s[i] == '+' || s[i] == '-' || s[i] == '/') l = s[i]; } Stack<int> st = new Stack<int>(); int[] sign = new int[256]; int[] mp = new int[256]; Array.Fill(sign, -1); char[] operand = { '*', '+', '-', '/' }; for (int p = 0; p < n; p++) { foreach (char x in operand) { mp[x] = 0; if (x == s[p]) sign[x] = p; } if (s[p] == '(') st.Push(p); else if (s[p] == ')') { int i = st.Pop(); int j = p; int nxt = nxta[j]; int last = lasta[i]; // Iterate in operator array foreach (char x in operand) { if (sign[x] >= i) mp[x] = 1; } int ok = 0; if (i > 0 && j + 1 < n && s[i - 1] == '(' && s[j + 1] == ')') ok = 1; if (mp['+'] == 0 && mp['*'] == 0 && mp['-'] == 0 && mp['/'] == 0) ok = 1; if (last == -1 && nxt == -1) ok = 1; if (last == '/') { } else if (last == '-' && (mp['+'] == 1 || mp['-'] == 1)) { } else if (mp['-'] == 0 && mp['+'] == 0) { ok = 1; } else { if ((last == -1 || last == '+' || last == '-') && (nxt == -1 || nxt == '+' || nxt == '-')) ok = 1; } // If the pair is redundant if (ok == 1) { ans[i] = 0; ans[j] = 0; } } } // Final string StringBuilder res = new StringBuilder(); for (int i = 0; i < n; i++) { if (ans[i] > 0) res.Append(s[i]); } return res.ToString(); } // Driver code public static void Main(string[] args) { string expression = "(A*(B+C))"; // Function call string result = removeBrackets(expression); Console.WriteLine(result); }}// This code is contributed by Utkarsh Kumar |
Javascript
function removeBrackets(exp) { let s = exp.split(''); let n = s.length; let ans = new Array(n + 1).fill(1); let lasta = new Array(n + 1); let nxta = new Array(n + 1); let l = -1; // Start Iterating from // starting index for (let i = 0; i < n; i++) { lasta[i] = l; if (s[i] == '*' || s[i] == '+' || s[i] == '-' || s[i] == '/') l = s[i]; } // Start Iterating from // last index l = -1; for (let i = n - 1; i >= 0; i--) { nxta[i] = l; if (s[i] == '*' || s[i] == '+' || s[i] == '-' || s[i] == '/') l = s[i]; } let st = []; let sign = new Array(256).fill(-1); let mp = new Array(256).fill(0); let operand = ['*', '+', '-', '/']; for (let p = 0; p < n; p++) { for (let x of operand) { mp[x] = 0; if (x == s[p]) sign[x] = p; } if (s[p] == '(') st.push(p); else if (s[p] == ')') { let i = st.pop(); let j = p; let nxt = nxta[j]; let last = lasta[i]; // Iterate in operator // array for (let x of operand) { if (sign[x] >= i) { mp[x] = 1; } } let ok = 0; if (i > 0 && j + 1 < n && s[i - 1] == '(' && s[j + 1] == ')') ok = 1; if (mp['+'] == 0 && mp['*'] == 0 && mp['-'] == 0 && mp['/'] == 0) ok = 1; if (last == -1 && nxt == -1) ok = 1; if (last == '/') { } else if (last == '-' && (mp['+'] == 1 || mp['-'] == 1)) { } else if (mp['-'] == 0 && mp['+'] == 0) { ok = 1; } else { if ((last == -1 || last == '+' || last == '-') && (nxt == -1 || nxt == '+' || nxt == '-')) ok = 1; } // If the pair is redundant if (ok == 1) { ans[i] = 0; ans[j] = 0; } } } // Final string let res = ""; for (let i = 0; i < n; i++) { if (ans[i] > 0) { res += s[i]; } } return res;}// Driver codelet expression = "(A*(B+C))";// Function calllet result = removeBrackets(expression);console.log(result);//This code is contributed by Tushar Rokade |
Output
A*(B+C)
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
