In most of the java interviews, the interviewer used to ask the basic implementation of the Java Stack operations along with its applications like checking the parenthesis string is balanced or not, Java string postfix to prefix expression using a stack, Java string prefix to postfix expression using a stack, etc. So, here is the post named as “Java Program to check the balanced parenthesis using Stack Algorithm” which contains both the basic Stack class implementation with all its operations with the code snippet which checks if a text contains the balanced parenthesis.
Implementation of Stack to check the balanced parenthesis using Linked List in Java:
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 81 82 83 84 85 | package stacks; import java.util.Scanner; //Node Implementation of the Stack using LinkedList class Node1{ char val; //character value to store the parenthesis values Node1 nextNode; //Link to the next node public Node1(char value){ this.val = value; this.nextNode = null; } } ////Class StackNew for different Stack operations class StackNew{ Node1 headNode = null; //Header or Top Node of the Stack //Push operation of the Stack public void push(char val){ Node1 newNode = new Node1(val); newNode.nextNode = headNode; headNode = newNode; } //Pop operation of the Stack public char pop(){ if(this.headNode == null){ System.out.println("UnderFlow! The Stack is Empty !"); return 0; }else{ char currentVal = this.headNode.val; this.headNode = this.headNode.nextNode; return currentVal; } } //Peek operation of the Stack i.e. returns the First element of the Stack public char peek(){ if(this.headNode == null){ System.out.println("UnderFlow! The Stack is Empty !"); return 0; }else{ return this.headNode.val; } } //isEmpty function of the stack to check whether the stack is empty or not public boolean isEmpty(){ if(this.headNode == null){ return true; }else{ return false; } } } //Implementation class to check whether the String with parenthesis is balanced or not public class BalancedBrackets { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String inputPattern = sc.nextLine(); char[] inputArray = inputPattern.toCharArray(); StackNew stack = new StackNew(); for(int i=0;i<inputArray.length;i++){ if(inputArray[i] == '[' || inputArray[i] == '{' || inputArray[i] == '('){ stack.push(inputArray[i]); }else if((stack.peek() == '[' && inputArray[i] == ']') || (stack.peek() == '{' && inputArray[i] == '}') || (stack.peek() == '(' && inputArray[i] == ')')){ stack.pop(); } } if(stack.isEmpty()){ System.out.println("Balanced Stack"); }else{ System.out.println("Un-Balanced Stack"); } } } |
The output of the above code Implementation (with different inputs):
1 2 3 4 5 6 7 8 | (()){}() Balanced Stack [()]{}{[()()]()} Balanced Stack [(]) Un-Balanced Stack |
Time Complexity: O(n)
Auxiliary Space: O(n) for the stack.
That’s it for now. Hope you understood the concepts of Java Program to check the balanced parenthesis using Stack Algorithm now. Comment below for help or the any other best implementation of the above code.
Read more on Computer Programming articles:-
Java Stack Implementation using Linked List
Java Stack Implementation using Array
Contribute to EduTechLearners:-
Please write comments if you want to share more information regarding the above notes. If you want some more notes/books on any of the topics please mail to us or comment below. We will provide you as soon as possible and if you want your’s notes to be published on our site then feel free to contribute on EduTechLearners or email your content to contribute@edutechlearners.com (The contents will be published by your Name).
Please suggest me which is good book for learn C-Programming