Java Data Structures Stacks | JavaTutorial

 Syntax to create an Stack:

// Create Integer type stack
Stack < Integer > myStack = new Stack<>();

The above code create an stack named myStack which can store integers.

Some more functions which we can use with stack:

• myStack.push(x) : Use push() to push an element into the stack.
• myStack.pop() : To remove an element from the top of the stack, we use the pop() method.
• myStack.peek() : The peek() method returns an object from the top of the stack.
• myStack.empty() : To check whether a stack is empty or not, we use the empty() method.

Now, try to solve the below problem using stack :

Given a string A consisting only of ’(‘ and ’)’.

You need to find whether parantheses in A is balanced or not ,if it is balanced then print 1 else print 0.

Examples of some correctly balanced strings are: “()()”, “((()))”, “((()))”

Examples of some unbalanced strings are: “()(“, “(())”, “((“, “)(“ etc.

Problem Constraints 1 <= Number of Testcases <= 100 1 <= |A| <= 105

Input Format First line of input consist of single integer T denoting the number of testcases. Each testcase has a single line of input containing an string A.

Output Format For each testcase output a single line i.e print 1 if parantheses in string are balanced else print 0.

Example Input

Input 1:

 2
 "(()())"
 "(()"

Example Output

Output 1:

 1
 0

Example Explanation

Explanation 1:

 Testcase 1: Given string (()()) is balanced so we print 1
 Testcase 2: Given string (() is not balanced so we print 0

Solution:

import java.lang.*;

import java.util.*;

public class Main {

    public static void main(String[] args) {

        // YOUR CODE GOES HERE

        // Please take input and print output to standard input/output (stdin/stdout)

        // DO NOT USE ARGUMENTS FOR INPUTS

        // E.g. 'Scanner' for input & 'System.out' for output

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        sc.nextLine();

        while(n-- > 0){

            String str = sc.nextLine();

            Stack<Character> st = new Stack<Character>();

            // System.out.println("Empty "+st.empty());

            boolean flag = true;

            for(int i=0;i<str.length();i++){

                Character ch = (Character)str.charAt(i);

                // System.out.println("Char: "+ch);

                if(ch == '('){

                    st.push(ch);

                }else if(ch == ')'){

                    if(st.empty() == false && st.peek() == '('){

                        st.pop();

                    }else{

                        flag = false;

                        break;

                    }                                        

                }             

            }          

            if(flag && st.empty())  

                System.out.println(1);

            else 

                System.out.println(0);

        }

    }

}