Redundant parentheses

#1

can u plz drop any hint to approch this prob means for what condition we have to look in the stack ,
is that it when we get simultaneously two )) and pop out twice???

#2

idea is to use stack here

We iterate through the given expression and for each character in the expression, if the character is a open parenthesis ‘(‘ or any of the operators or operands, we push it to the stack. If the character is close parenthesis ‘)’, then pop characters from the stack till matching open parenthesis ‘(‘ is found.
Now for redundancy two condition will arise while popping-

  1. If immediate pop hits a open parenthesis ‘(‘, then we have found a duplicate parenthesis.
    For example, (((a+b))+c) has duplicate brackets around a+b . When we reach second “)” after a+b, we have “ (( ” in the stack. Since the top of stack is a opening bracket, we conclude that there are duplicate brackets.

  2. If immediate pop doesn’t hit any operand(‘*’, ‘+’, ‘/’, ‘-‘) then it indicates the presence of unwanted brackets surrounded by expression.
    For instance, (a)+b contain unwanted () around a thus it is redundant.

function to check redundant paranthesis

bool checkRedundancy(string& str) 
{ 
    // create a stack of characters 
    stack<char> st; 
  
    // Iterate through the given expression 
    for (int i=0;str[i]!='\0'; i++) { 
  
        // if current character is close parenthesis ')' 
        if (ch == ')') { 
            char top = st.top(); 
            st.pop(); 
  
            // If immediate pop have open parenthesis '(' 
            // duplicate brackets found 
            bool flag = true; 
  
            while (top != '(') { 
  
                // Check for operators in expression 
                if (top == '+' || top == '-' ||  
                    top == '*' || top == '/') 
                    flag = false; 
  
                // Fetch top element of stack 
                top = st.top(); 
                st.pop(); 
            } 
  
            // If operators not found 
            if (flag == true) 
                return true; 
        } 
  
        else
            st.push(ch); // push open parenthesis '(', 
                  // operators and operands to stack 
    } 
    return false; 
}

if you have more doubts regarding this feel free to ask
i hope this helps
if yes hit a like :heart:: and don’t forgot to mark doubt as resolved :grinning:

#3

sir ye jo 2 condition di hui hai vo to smz aa rhi hai lekin code me thodi problem hai like if we get ch==’)’ then why did we do poping first without checking any cond??

#4

can u plz make it more understandable to me…

#5

if we encounter ‘)’ then we have to definitely pop() but to check the condition we are storing the top element of stack in variable “top”

#6

done but sir jo que sir ne lec me krvaye hai unke alawa mujhe idea nhi ki kahan pe stack queue use kr skte hai ,isme confidence build nhi ho rha so can u plz help me with this…

#7

practice makes the man perfect
try to solve question on your own
do something even wrong no matter
if you done wrong then only you can understand the correct approach and don’t do that mistake again