Home » Technical Interview Questions » Stack Interview Questions » Identify and Mark Unmatched Parenthesis in an Expression

Identify and Mark Unmatched Parenthesis in an Expression


Difficulty Level Medium
Stack String TCS

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

Identify and Mark Unmatched Parenthesis in an Expression

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.
READ  How to Implement Stack Using Priority Queue or Heap?

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup