Identify and mark unmatched parenthesis in an expression

Last Updated on October 10, 2022 by Gokul Kannan

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.

Examples:

Input : ((x)
Output : -10×1

Input : (x))
Output : 0x1-1

Input : (((abc))((z)))))
Output: 000abc1100z111-1-1

Algorithm:-

We will use a Stack data structure to solve this question.

1. Start traversing through the given string and every time when ‘(‘ is encountered then push the current index in the stack.
2. If ‘)‘ 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 ‘(‘ brackets.
3. If the stack is empty, and we encounter a closing bracket ‘)’ we replace -1 at that index of the string because this is contributing the unmatched brackets.

Dry Run

Code Implementation

#include 
using namespace std;
 
void identifyMarkParenthesis(string a){
    // stack to store index
    stack index;
 
    // traverse through the whole string
    for (int i = 0; i < a.length(); i++) {
 
        // if a[i] is opening bracket '(' 
        // then just push into stack
        if (a[i] == '('){
            index.push(i);
        }         
        // if a[i] is closing bracket ')'
        else if (a[i] == ')') {
            if (index.empty()){
            // If this closing bracket is  
           // unmatched then mark -1
                a.replace(i, 1, "-1");
            }else{
                // replace all opening 
              // brackets with 0
             // and closing brackets with 1
                a.replace(i, 1, "1");
                a.replace(index.top(), 1, "0");
                index.pop();
            }
        }
    }
    // if stack is not empty then pop 
  //out all elements from it and replace-1
 // at that index of the string because    // they are unmatched
    while (!index.empty()) {
        a.replace(index.top(), 1, "-1");
        index.pop();
    }
 
    // print final string
    cout << a << endl;
}
 

int main(){
    string str = "(x))";
    identifyMarkParenthesis(str);
    return 0;
}

Output:
0x1-1

Time Complexity: O(n)
Space Complexity: O(n)

We tried to discuss the Identify and mark unmatched parenthesis in an expression. We hope this article gives you a better understanding of the Identify and mark unmatched parenthesis in an expression PrepBytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program which will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.