-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathStack-Check redundant brackets
63 lines (58 loc) · 2.14 KB
/
Stack-Check redundant brackets
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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.
Note:
You are not required to print the expected result. It has already been taken care of.
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
***********************************Code************************************
import java.util.Stack;
public static boolean checkRedundantBrackets(String expression) {
Stack<Character> stack=new Stack<Character>();
int count=0;
for(int i=0;i<expression.length();i++)
{
char c=expression.charAt(i);
if (c==')')
{
while(!stack.isEmpty() && stack.peek()!='(')
{
count=count+1;
stack.pop();
}
if (count==0 || count==1)
{
return true;
}
stack.pop();
count=0;
}
else
{
stack.push(c);
}
}
return false;
}