{"id":10068,"date":"2022-09-28T10:55:49","date_gmt":"2022-09-28T10:55:49","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=10068"},"modified":"2022-10-10T09:40:31","modified_gmt":"2022-10-10T09:40:31","slug":"expression-contains-redundant-bracket-or-not","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/expression-contains-redundant-bracket-or-not\/","title":{"rendered":"Expression contains redundant bracket or not"},"content":{"rendered":"

\"\"<\/p>\n

Note<\/strong>: Expression may contain any of these \u2018+\u2018, \u2018*\u2018, \u2018\u2013\u2018, and \u2018\/\u2018 operators. Given expression is valid and there are no white spaces present.<\/p>\n

Examples:<\/h3>\n

Input<\/strong>: \u201c((a+b+c))\u201d
\nOutput<\/strong>: YES<\/p>\n

Explanation<\/strong>:
\n((a+b+c)) can be reduced to (a+b+c) by removing outer redundant brackets ( (a+b+c) ). <\/p>\n

Input<\/strong>: \u201c(a+(b)\/c)\u201d
\nOutput<\/strong>: YES<\/p>\n

Explanation<\/strong>:
\n(a+(b)\/c) can be reduced to (a+b\/c) by removing outer redundant brackets of b i.e (a+ ( b ) \/c).<\/p>\n

Input<\/strong>: \u201c((a+b) * c+z)\u201d
\nOutput<\/strong>: NO<\/p>\n

Before going to the solution we need to understand the question by analysing the above examples. One thing is clear if \u2018()\u2019 contains operands only in that case these brackets are redundant. For example \u201c((a+b)*c+z)\u201d contains no redundant brackets because its inner and outer brackets contain operands and operators. <\/p>\n

We will use the Stack data structure<\/a> to solve this question. For any expression, if we are able to pick any sub-expression of this expression surrounded by (), then we are again left with ( ) as part of the string, which means it has no operands and operators between them so this is redundant brackets. <\/p>\n

Algorithm:<\/h3>\n
    \n
  1. \n

    Start iterating through the given expression and for each character in the expression<\/p>\n

      \n
    • Start pushing every character of the string in the stack.<\/li>\n
    • But, If the character is a close parenthesis \u2018)\u2019, then pop every character from the stack till matching open parenthesis i.e \u2018(\u2018 is found.<\/li>\n<\/ul>\n<\/li>\n
    • \n

      Now for redundancy two conditions will arise while popping.<\/p>\n

        \n
      • If immediate pop hits an open parenthesis \u2018(\u2018, then we have found a duplicate parenthesis. For example, (((a+b))+c) has duplicate brackets around a+b. When we reach the second \u201c)\u201d after a+b, we have \u201c((\u201d in the stack. This means that is the redundant bracket.<\/li>\n
      • If immediate pop doesn\u2019t hit any operand with the operator (\u2018*\u2019, \u2018+\u2019, \u2018\/\u2019, \u2018-\u2018) then it indicates the presence of unwanted brackets surrounded by expression. For instance, (a)+b contains unwanted () around a thus it is redundant. <\/li>\n<\/ul>\n<\/li>\n<\/ol>\n

        Dry Run<\/h3>\n

        \"\"<\/p>\n

        Code Implementation<\/h3>\n\t\t\t\t\t\t