https://www.prepbytes.com/data-structures-in-java
Problem statement
Given an expression containing only β(β, β)β, β{β, β}β, β[β, β]β , check whether the expression is balanced or not.
An expression is balanced if each opening bracket is closed by the same type of closing bracket in the exact same order.
Input: A string representing the given expression
Output: Boolean value
Test cases:
Input 1:
β({[]})β
Output 1:
true
Input 2:
β(){}](β
Output 2:
false
Approach – Using Stack
The idea is to use the LIFO functionality of the stack. As a stack is LIFO data structure, we will remove every opening bracket (β(β, β{β, β[β), whenever we encounter the same type of closing bracket (β)β, β}β, β]β).
If for any opening bracket we don’t have a closing bracket, the opening bracket will remain in the stack forever.
Similarly if we only have a closing bracket without a preceding opening bracket we will just push the closing bracket into the stack and it will remain there forever.
So, at last after traversing the whole expression, if the stack is empty then it will mean that the given expression is balanced, otherwise if the stack contains elements that would mean the given expression was unbalanced.
Algorithm
- Initialize an empty stack.
- Iterate i from 0 to length(expression).
a. Store the current character in a variable βchβ.
b. If stack is empty: Push βchβ to the stack
c. Else if current character is a closing bracket and of the top of the stack contains an opening bracket of the same type
Remove the top of the stack: Else, push βchβ to the stack - If the stack is empty, return true, else false.
Dry Run
Input: β({[]})β
Output: true
Stack | Expression | Action |
---|---|---|
({[]}) | Push | |
( | {[]}) | Push |
({ | []}) | Push |
({[ | ]}) | Pop |
({ | }) | Pop |
( | ) | Pop |
Empty |
As the stack is empty, hence the given expression was balanced.
Code Implementation:
import java.util.*; public class Main { public static void main(String[] args) { String exp = "({[]})"; System.out.println(isBalanced(exp)); } // Function to check whether given expression is balanced or not public static boolean isBalanced(String exp) { Stack<Character> st = new Stack<>(); // Traverse over the expression for(int i = 0; i < exp.length(); i++){ // Get the current character char ch = exp.charAt(i); // If the stack is empty, push the current character into the stack if(st.isEmpty()){ st.push(ch); } // Otherwise if the current character is a closing bracket // and of the top of the stack contains an opening bracket of the same type // then remove the top of the stack else if((ch==')' && st.peek() == '(')||(ch=='}' && st.peek() == '{')||(ch==']' && st.peek() == '[')){ st.pop(); } else{ st.push(ch); } } // If after traversing the whole expression the stack is empty // then it means the given expression is balanced else unbalanced return (st.isEmpty()); } }
Output:
true
Time complexity: O(n). We can observe that every character is pushed and removed from the stack at most once. Hence, the total operations being performed is 2n and O(2n) = O(n) because we donβt consider constant terms during asymptotic analysis of time complexity.
Space Complexity: O(n). O(n) space is required for the input and output array. The auxiliary space complexity is also O(n) as we are using a stack. At any point of time the stack can contain at most n elements.
So, in this blog, we have tried to explain the efficient way to check for balanced parentheses in an expression. Hope this blog helps you understand and solve the problem. To practice more problems you can check outMYCODE | Competitive Programming at Prepbytes.