« Check Redundant Brackets

Check redundant brackets

For a given expression in the form of a string, find if there exist any redundant brackets or not. It is given that the expression contains only rounded brackets or parenthesis and the input expression will always be balanced.

A pair of the bracket is said to be redundant when a sub-expression is surrounded by unnecessary or needless brackets.

Example:

Expression: (a+b)+c

Since there are no needless brackets, hence, the output must be 'false'.

Expression: ((a+b))

The expression can be reduced to (a+b). Hence the expression has redundant brackets and the output will be 'true'.

Note:

You will not get a partial score for this problem. You will get marks only if all the test cases are passed.

Input Format :

The first and the only line of input contains a string expression, without any spaces in between.

Output Format :

The first and the only line of output will print either 'true' or 'false'(without the quotes) denoting whether the input expression contains redundant brackets or not.

Constraints:

0 <= N <= 10^6

Where N is the length of the expression.

Time Limit: 1 second

Sample Input 1:

a+(b)+c

Sample Output 1:

true

Explanation:

The expression can be reduced to a+b+c. Hence, the brackets are redundant.

Sample Input 2:

(a+b)

Sample Output 2:

false

Copy
1#include <iostream>
2#include <string>
3#include<stack>
4using namespace std;
5
6bool checkRedundantBrackets(string expression) {
7    // Write your code here
8    stack<char> st;
9    for(int i=0; i<expression.length(); i++){
10        if(expression[i] == '(' || expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || expression[i] == '/'){
11          st.push(expression[i]);
12        }else if(expression[i] == ')'){
13          bool hasOperator = false;
14
15          while (!st.empty() && st.top() != '(') {
16            st.pop();
17            hasOperator = true;
18            }
19            if(!hasOperator){
20                return true;
21            }
22            if(!st.empty()){
23                st.pop();
24            }
25        }
26    }
27    return false;
28}
29
30int main() {
31    string input;
32    cin >> input;
33    cout << ((checkRedundantBrackets(input)) ? "true" : "false");
34}