Identify and Mark Unmatched Parenthesis in an Expression

In identify and mark unmatched parenthesis in an expression problem, we have given a string s of length n containing an expression. Find the balanced pair of parenthesis and replace all the balanced opening parenthesis as 0, the balanced closing parenthesis as 1 and the unbalanced parenthesis as -1.

Example

Let the given string s = “(((abc))((d)))))” and here we identify and mark unmatched parenthesis in an expression using given string.

Here, the first parenthesis balances with the last third parenthesis. Therefore, replace the opening and closing parenthesis with 0 and 1 respectively.

• After that, the second parenthesis balances with the second closing parenthesis of subexpression “abc” therefore, replace the opening and closing parenthesis with 0 and 1 respectively.
• Similarly, the third parenthesis balances with first closing parenthesis of subexpression “abc” therefore, replace the opening and closing parenthesis with 0 and 1 respectively.
• The fourth opening parenthesis balances with the second closing parenthesis of subexpression “d” therefore, replace the opening and closing parenthesis with 0 and 1 respectively.
• Similarly, the fifth opening parenthesis balances with first closing parenthesis of subexpression “d” therefore, replace the opening and closing parenthesis with 0 and 1 respectively.
• Finally, replace all the unbalanced parenthesis as -1.
• Therefore the result = 000abc1100d111-1-1

Input : s = “((a)”

Output : -10a1

Input : s = “(a))”

Output : 0a1-1

Algorithm for Identify and Mark Unmatched Parenthesis in an Expression

1. Initialize a string s of length n containing an expression.
2. Create a stack data structure.
3. Traverse through the given string and check if the character at the current index in the string is equal to the opening parenthesis, push/insert the current index in the stack.
4. Else check if the character at the current index in the string is equal to the closing parenthesis, check if the stack is empty, replace or update the character at the current index in the string as -1. Else replace all the opening parenthesis with 0 and closing parenthesis with 1.
5. While the stack is not empty, update all the characters in the stack as -1.
6. Print the updated string.

C++ Program to Identify and Mark Unmatched Parenthesis in an Expression

#include <bits/stdc++.h> 
using namespace std; 
  
void identifyParenthesis(string s){
    stack<int> st; 
  
    for(int i = 0; i < s.length(); i++){ 
        if(s[i] == '('){  
            st.push(i); 
        }
          
        else if(s[i] == ')'){ 
  
            if(st.empty()){  
                s.replace(i, 1, "-1"); 
            }
              
            else{ 
                s.replace(i, 1, "1"); 
                s.replace(st.top(), 1, "0"); 
                st.pop(); 
            } 
        } 
    } 
  
    while(!st.empty()){ 
        s.replace(st.top(), 1, "-1"); 
        st.pop(); 
    } 
  
    cout << s << endl; 
} 
  
int main(){ 
    string s = "(a))"; 
    
    identifyParenthesis(s); 
    
    return 0; 
}

0a1-1

Java Program to Identify and Mark Unmatched Parenthesis in an Expression

import java.util.*; 
  
class MarkParenthesis{ 
    
    static void identifyParenthesis(StringBuffer s){  
        Stack<Integer> st = new Stack<Integer>();  
      
        for(int i = 0; i < s.length(); i++){  
            if (s.charAt(i) == '('){  
                st.push(i);  
            }
              
            else if(s.charAt(i) == ')'){  
                if(st.empty()){  
                    s.replace(i, i + 1, "-1");  
                }
                  
                else{  
                    s.replace(i, i + 1, "1");  
                    s.replace(st.peek(), st.peek() + 1, "0");  
                    st.pop();  
                }  
            }  
        }  
      
        while(!st.empty()){  
            s.replace(st.peek(), 1, "-1");  
            st.pop();  
        }  
      
        System.out.println(s); 
    }  
      
    public static void main(String[] args){
        
        StringBuffer s = new StringBuffer("(a))");  
        identifyParenthesis(s);  
        
    } 
}

0a1-1

Complexity Analysis

Time Complexity: O(n) where n is the number of characters in the given expression.

Space Complexity: O(n) because we used space to store n elements.

References