Skip to main content

Expression Validation - Java Stack Problem

Problem Statement
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)
A string containing only parentheses is balanced if the following is true: 1. if it is an empty string 2. if A and B are correct, AB is correct, 3. if A is correct, (A) and {A} and [A] are also correct.
Examples of some correctly balanced strings are: "{}()", "[{()}]", "({()})" 
Examples of some unbalanced strings are: "{}(", "({)}", "[[", "}{" etc.
Given a string, determine if it is balanced or not.
Input Format
There will be multiple lines in the input file, each having a single non-empty string. You should read input till end-of-file.
The part of the code that handles input operation is already provided in the editor.
Output Format
For each case, print 'true' if the string is balanced, 'false' otherwise.
Sample Input
{}()
({()})
{}(
[]
Sample Output
true
true
false
true


import java.util.*;
class Solution{
  
    static boolean validateExpression(String str){
        char[] chrArray=str.toCharArray();
        int par=0,cur=0,bra=0;
        for(int i=chrArray.length-1;i>=0;i--){
            if(chrArray[i]==')'){
                par++;
            }else if(chrArray[i]=='}'){
                cur++;
            }else if(chrArray[i]==']'){
                bra++;
            }
           
            if(chrArray[i]=='('){
                par--;
            }else if(chrArray[i]=='{'){
                cur--;
            }else if(chrArray[i]=='['){
                bra--;
            }
        }
        return par==bra && bra==cur;
    }
   
   public static void main(String []argh)
   {
      Scanner sc = new Scanner(System.in);
     
      while (sc.hasNext()) {
         String input=sc.next();
            //Complete the code
            System.out.println(validateExpression(input));
      }
     
   }
}

Input (stdin)
{}()
({()})
{}(
[]
Your Output (stdout)
true
true
false
true
Expected Output
true
true
false
true


• Score: 20.00/20.00
Test Case #0:  0.08s
Test Case #1:  0.08s
Test Case #2:  0.08s


Comments

Post a Comment

Popular posts from this blog

CODILITY: Determine whether given string of parentheses is properly nested.

Task description A string S consisting of N characters is called  properly nested  if: S is empty; S has the form " (U) " where U is a properly nested string; S has the form " VW " where V and W are properly nested strings. For example, string " (()(())()) " is properly nested but string " ()) " isn't. Write a function: class Solution { public int solution(String S); } that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise. For example, given S = " (()(())()) ", the function should return 1 and given S = " ()) ", the function should return 0, as explained above. Assume that: N is an integer within the range [ 0 .. 1,000,000 ]; string S consists only of the characters " ( " and/or " ) ". Complexity: expected worst-case time complexity is O(N); expected worst-case space complexity is O(1) (not counting the storage requi...
1 comment
Read more

Distinct: Compute number of distinct values in an array.

Task description Write a function class Solution { public int solution(int[] A); } that, given a zero-indexed array A consisting of N integers, returns the number of distinct values in array A. Assume that: N is an integer within the range [ 0 .. 100,000 ]; each element of array A is an integer within the range [ −1,000,000 .. 1,000,000 ]. For example, given array A consisting of six elements such that: A[0] = 2 A[1] = 1 A[2] = 1 A[3] = 2 A[4] = 3 A[5] = 1 the function should return 3, because there are 3 distinct values appearing in array A, namely 1, 2 and 3. Complexity: expected worst-case time complexity is O(N*log(N)); expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified. class Solution { public int solution ( int [] A) { // write your code in Java SE 8 int len=A.length; int count= 1 ; ...
1 comment
Read more

Dominator: Find an index of an array such that its value occurs at more than half of indices in the array.

Dominator Find an index of an array such that its value occurs at more than half of indices in the array. Task description A zero-indexed array A consisting of N integers is given. The dominator  of array A is the value that occurs in more than half of the elements of A. For example, consider array A such that A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3 The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8. Write a function class Solution { public int solution(int[] A); } that, given a zero-indexed array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator. Assume that: N is an integer within the range [ 0 .. 100,000 ]; each element of array A is an integer within the range [ −2,147,483,648 .. 2,147,483...
Post a Comment
Read more