Code Challenge: Find whether the given expression is balanced by@srebalaji

Code Challenge: Find whether the given expression is balanced

June 23rd 2022 11,756 reads
Read on Terminal Reader
react to story with heart
react to story with light
react to story with boat
react to story with money
image
Srebalaji Thirumalai HackerNoon profile picture

Srebalaji Thirumalai

image
Stacks!!
Hey, guys
Lately, I was solving some algorithm challenges in hackerrank.com.
I just has a thought of sharing a simple challenge with the medium community. :)

Problem Statement

Given a string expression, find whether the given expression is balanced or not.
Sample-1

Input:{ [ ( ) ] }

Output:True
Sample-2

Input:{ [ } ]

Output:False
Sample-3

Input:{ { [ ]

Output:False
Try to solve this problem before looking in to the solution.

Solution

This problem is so simple. For every opening brackets, you have to check whether the corresponding closing brackets are present in order.
We can solve this problem using Stack. If you want a recap about stack no problem take a look at .
First, we start by iterating through the string and if we find an opening bracket we push it to the stack. And if we find a closing bracket we are popping the top element from the stack to check whether the closing bracket is associated with the opening bracket (top element popped). If not, we are returning false or else we continue.
And remember after iterating through the entire string, we have to check the size of the stack. If the size of the stack is not zero (i.e) not empty it means that some closing brackets are missing.
If you don’t get it stay with me :)
Pseudo Code:
expression = { [ ( ) ] }



for each element in the stringi=0We have an opening braces so we push it to the stack.Stack: {





















i=1We have an opening braces so we push it to the stack.Stack: [{i=2We have an opening braces so we push it to the stack.Stack: ([{i=3We have an closing braces so we pop the element from stack.Popped element: (Closing braces: )We continue to iterate because the opening braces is associated with the closed braces.Stack: [{i=4We have an closing braces so we pop the element from stack.Popped element: [Closing braces: ]We continue to iterate because the opening braces is associated with the closed braces.Stack: {





i=5We have an closing braces so we pop the element from stack.Popped element: {Closing braces: }We continue to iterate because the opening braces is associated with the closed braces.Stack: Empty
The stack is empty which means that we have an equal equal number of closing braces for all opening braces.
Code Implementation In Java:
import java.util.*;










class BalancedExpression {public static void main(String args[]) {System.out.println("Balanced Expression");Scanner in = new Scanner(System.in);String input = in.next();if (isExpressionBalanced(input)) {System.out.println("The expression is balanced");}else {System.out.println("The expression is not balanced");}










static boolean isExpressionBalanced(String input) {Stack stack = new Stack();for (int i=0; i<input.length(); i++) {if (input.charAt(i) == '(' || input.charAt(i) == '{'|| input.charAt(i) == '[') {stack.push(input.charAt(i));}if (input.charAt(i) == ')' || input.charAt(i) == '}'|| input.charAt(i) == ']') {if (stack.empty()) {return false;}char top_char = (char) stack.pop();
 if ( (top\_char == '(' && input.charAt(i) != ')') || (top\_char == '{' && input.charAt(i) != '}') || (top\_char == '\[' && input.charAt(i) != '\]') ) {  
  return false;  
 }     
}  




}return stack.empty();}}}
You can see the source code here
If you are interested in more competitive challenges you can subscribe to my newsletter DS Weekly to get a solved competitive programming challenge weekly. :) :)
react to story with heart
react to story with light
react to story with boat
react to story with money
L O A D I N G
. . . comments & more!