Question

Write a function that determines if a string has the same number of 0’s and 1’s using a stack. The function must run in O(N) time. You can assume there already exists a stack class and can just use it

(Java Please)

Answer 1

Explanation::

Code in JAVA is given below

Please read comments for better understanding of the code

NOTE: Assumption is made that string consist only of 1's and 0's

Code in JAVA::

import java.util.Scanner;

import java.util.Stack;

public class StackCounter {

public static void main(String[] args) {

/**

* Using Scanner class object named sc to take input from the user

* */

Scanner sc = new Scanner(System.in);

/**

* An String variable named binary is declared below

* */

String binary;

/**

* Below we ask user to enter the binary String

* */

System.out.print("Enter binary string (1's and 0's) : ");

binary = sc.nextLine();

/**

* An integer variable named halfLength is declared below

* It stores the division of length of string binary by 2

* */

int halfLength = binary.length()/2;

/**

* If binary is odd length string then no need to use stack at all

* */

if(binary.length()%2!=0){

System.out.println("No equal number of 1's and 0's. ODD LENGTH STRING!");

}else{

/**

* An Stack of type Character named binaryStack is declared below

* We will populate in it only 1's

* */

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

/**

* Using for loop we will traverse through the stack

* and perform push for only '1'

* */

char ch;

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

/**

* we store current character at index i in binary string

* into ch variable

* */

ch = binary.charAt(i);

if(ch=='1'){

/**

* If ch is 1 then push into stack

* */

binaryStack.push(ch);

}

}

/**

* Now if size of the stackBinary and half length of string binary is same

* then there are equal number of 1's and 0's

* */

if(halfLength == binaryStack.size()){

System.out.println("Equal number of 1's and 0's!!!");

}else{

System.out.println("No equal number of 1's and 0's.");

}

}

}

}

OUTPUT::

Test Case 1:

Enter binary string (1's and 0's) : 101

No equal number of 1's and 0's. ODD LENGTH STRING!

Test Case 2:

Enter binary string (1's and 0's) : 1010

Equal number of 1's and 0's!!!

Test Case 3:

Enter binary string (1's and 0's) : 1000111100

Equal number of 1's and 0's!!!

Please provide feedback!!

Thank You!!