Stacks

Problem Description

In computer science, a stack or LIFO (last in, first out) is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the last element that was added.(Wikipedia)

Syntax to create a Stack:

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

The above code create a 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

Start solving Stacks on Interview Code Editor

Hints

Hint 1
Solution Approach
Complete Solution

Stacks

Discussion