Stack: Check if the expression contains redundant bracket or not

Problem Statement:

You are given a string, you need to check if the string contains redundant parenthesis or not

Example:

Input : ((a + b))

Output: yes

Solution Explanation:

Iterate through the given expression

If the character is “(” or operand or operator push into the stack.

If character is “)”, check if the parentheses are redundant.

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

Code Solution

#include <iostream>
#include <vector>
#include <stack>
using namespace std;


bool solution(string& s)
{
    stack<char> st;

    for (auto& ch : s) 
    {

        if (ch == ')') 
        {
            char top = st.top();
            st.pop();

            bool flag = true;

            while (!st.empty() and top != '(') 
            {

                if (top == '+' || top == '-' || 
                    top == '*' || top == '/')
                    flag = false;

                top = st.top();
                st.pop();
            }

            if (flag == true)
                return true;
        }

        else
            st.push(ch); 
             
    }
    return false;
}


int main()
{
    string s = "((a+b))";
    
    bool res = solution(s);

    if (res == true)
        cout << "True\n";
    else
        cout << "False\n";    
    return 0;
}

Output

True