Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# 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.

### 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.