{"id":10071,"date":"2022-09-28T11:24:03","date_gmt":"2022-09-28T11:24:03","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=10071"},"modified":"2022-10-10T09:41:24","modified_gmt":"2022-10-10T09:41:24","slug":"identify-and-mark-unmatched-parenthesis-in-an-expression","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/identify-and-mark-unmatched-parenthesis-in-an-expression\/","title":{"rendered":"Identify and mark unmatched parenthesis in an expression"},"content":{"rendered":"

\"\"<\/p>\n

Given an expression, find and mark matched and unmatched parenthesis in it. We need to replace all balanced opening parenthesis with 0, balanced closing parenthesis with 1, and all unbalanced with -1. This is one of the most important questions to learn while preparing for interviews.<\/p>\n

Examples:<\/h3>\n

Input<\/strong> : ((x)
\nOutput<\/strong> : -10×1<\/p>\n

Input<\/strong> : (x))
\nOutput<\/strong> : 0x1-1<\/p>\n

Input<\/strong> : (((abc))((z)))))
\nOutput<\/strong>: 000abc1100z111-1-1<\/p>\n

Algorithm:-<\/h3>\n

We will use a Stack<\/a> data structure to solve this question.<\/p>\n

    \n
  1. Start traversing through the given string and every time when \u2018(\u2018 is encountered then push the current index in the stack. <\/li>\n
  2. If \u2018)\u2018 is encountered then replace all opening brackets with 0 and closing brackets with 1 while doing this pop the index of the opening brackets from the stack because they refer to open \u2018(\u2018 brackets.<\/li>\n
  3. If the stack is empty, and we encounter a closing bracket \u2018)\u2019 we replace -1 at that index of the string because this is contributing the unmatched brackets. <\/li>\n<\/ol>\n

    Dry Run<\/h3>\n

    \"\"<\/p>\n

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