Remove all redundant parenthesis

0 0 10 minutes read

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 brackets
string 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 code
int 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 approach
import 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 code
if __name__ == '__main__':
    expression = "(A*(B+C))"
 
    # Function call
    result = Solution.removeBrackets(expression)
 
    print(result)

C#

// C# code of the above approach
using 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 code
let expression = "(A*(B+C))";
 
// Function call
let 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)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!