-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathStack-Brackets Balanced
80 lines (72 loc) · 2.74 KB
/
Stack-Brackets Balanced
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
For a given a string expression containing only round brackets or parentheses, check if they are balanced or not. Brackets are said to be balanced if the bracket which opens last, closes first.
Example:
Expression: (()())
Since all the opening brackets have their corresponding closing brackets, we say it is balanced and hence the output will be, 'true'.
You need to return a boolean value indicating whether the expression is balanced or not.
Note:
The input expression will not contain spaces in between.
Input Format:
The first and the only line of input contains a string expression without any spaces in between.
Output Format:
The only line of output prints 'true' or 'false'.
Note:
You don't have to print anything explicitly. It has been taken care of. Just implement the function.
Constraints:
1 <= N <= 10^7
Where N is the length of the expression.
Time Limit: 1sec
Sample Input 1 :
(()()())
Sample Output 1 :
true
Sample Input 2 :
()()(()
Sample Output 2 :
false
Explanation to Sample Input 2:
The initial two pairs of brackets are balanced. But when you see, the opening bracket at the fourth index doesn't have its corresponding closing bracket which makes it imbalanced and in turn, making the whole expression imbalanced. Hence the output prints 'false'.
***********************************************************Code*****************************************************
import java.util.Stack;
public class Solution {
public static boolean isBalanced(String expression) {
Stack<Character> stack=new Stack<Character>();
for (int j=0;j<expression.length();j++)
{
char i=expression.charAt(j);
if (i=='[' || i=='{' || i=='(')
{
stack.push(i);
}
else if(i==']' || i=='}' || i==')')
{
if (stack.isEmpty())
return false;
else
{
if (i==']')
{
if (stack.peek()!='[')
return false;
else
stack.pop();
}
else if (i=='}')
{
if (stack.peek()!='{')
return false;
else
stack.pop();
}
else if (i==')')
{
if (stack.peek()!='(')
return false;
else
stack.pop();
}
}
}
}
return stack.isEmpty();
}
}