6
\$\begingroup\$

I recently wrote a code in online recruitment test. It was very good.

With each question, there were associated space and time limits check. If our code executed correctly within both limits, only then we were given full marks otherwise 0.

Input: String consisting of ASCII characters.

Output: True if the string is balanced parenthesis wise and false otherwise.

I wrote the following code for the problem, but the problem is I got 0 marks because it said limits crossed, Optimization required.

import java.util.*;
import java.io.*;
class Prths
{
 private static Stack<Boolean> st=new Stack<Boolean>();
 public static void main(String []args)throws IOException
 {
     BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
     String s=br.readLine();
     boolean result=check(s);
     System.out.println(result);
 }
 public static boolean check(String s)
 {
     int i=0;
     while(i<s.length())
     {
         if(s.charAt(i)==')'&&st.isEmpty())
          return false;
         else if(s.charAt(i)==')')
          st.pop();
         else if(s.charAt(i)=='(')
          st.push(true);
         ++i;
     }
     if(st.isEmpty())
      return true;
     else return false;
 }
}
\$\endgroup\$
  • \$\begingroup\$ Will the inputs a(), (a) and ()a all return true? \$\endgroup\$ – h.j.k. Oct 1 '15 at 8:07
  • \$\begingroup\$ @h.j.k. Yes they will. \$\endgroup\$ – Sumeet Oct 1 '15 at 8:08
  • \$\begingroup\$ Are you on Java 8? \$\endgroup\$ – h.j.k. Oct 1 '15 at 8:08
  • \$\begingroup\$ It was online editor.So I do not know. \$\endgroup\$ – Sumeet Oct 1 '15 at 8:09
  • 2
    \$\begingroup\$ Prths? Please no. Use well-known and widely-used abbreviations if you must, but Prths is neither. Someone skimming your API documentation is going to have no idea what it is or what it's for. \$\endgroup\$ – Blacklight Shining Oct 1 '15 at 20:03
11
\$\begingroup\$
 if(st.isEmpty())
  return true;
 else return false;

This can be simplified to return st.isEmpty();... Wait, that's not the right advice.

Why do you even need a Stack when you can simply count?

public static boolean check(String s) {
    int counter = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            counter++;
        } else if (s.charAt(i) == ')') {
            if (counter == 0) {
                return false;
            }
            counter--;
        }
    }
    return counter == 0;
}

Other issues (which may or may not be picked up by the automatic assessment):

  • If this is assessed using Java 7, using try-with-resources is recommended for the BufferedReader instance.
  • You can inline the printing of the results, i.e. System.out.println(check(input));.
  • Please use braces consistently... that tends to improve code readability for human programmers.

edit: OK, second stab at a Java 8 stream-based solution...

// Using better-suited visibility modifier and method name
private static boolean balanced(String input) {
    return input.chars().mapToDouble(i -> i == '(' ? 1 : i == ')' ? -1 : 0).reduce(0,
            (a, b) -> a == 0 && b == -1 ? Double.NaN : a + b) == 0;
}

mapToDouble() is used here just so that Double.NaN can be used as a special placeholder to effectively ignore further computations when a ) is encountered without a matching (. It doesn't look as streamlined as I hoped it would be though, and I think for most intent and purposes the non-stream-based way works and reads just a little better.

\$\endgroup\$
  • 2
    \$\begingroup\$ Your stream-fu solution in Rev 2 would report that )( is balanced, which seems to go against my common sense as well as the behaviour of the original code. \$\endgroup\$ – 200_success Oct 1 '15 at 8:30
  • \$\begingroup\$ @200_success thanks for pointing that out... I've decided to rollback my answer to the earlier revision completely. \$\endgroup\$ – h.j.k. Oct 1 '15 at 8:33
  • \$\begingroup\$ And reintroducing second stab at Java 8-based solution... \$\endgroup\$ – h.j.k. Oct 1 '15 at 8:59
7
\$\begingroup\$

This line is the source of your woes:

private static Stack<Boolean> st=new Stack<Boolean>();

In particular, making the stack static is wrong. The stack, and whatever is in it, persists across calls to check(). So, check(")))") and check("(((") will each return false as expected, but if you then call check(")))"), it would return true!

java.util.Stack is to be avoided. It was the result of some poor design decisions back in JDK 1.0. It extends Vector, which exposes methods that violate the stack abstraction. Also, Vector methods are synchronized, which causes unnecessary overhead when thread safety is not needed. As recommended in the JavaDoc, use a Deque wherever you need a stack.

Furthermore, the items that you stuff into this stack (namely Boolean.TRUE objects) are completely ignored. The only thing that matters is the size of the stack. For that, you don't need a stack at all; a simple int counter will do.

\$\endgroup\$
4
\$\begingroup\$

Using Stack is a pure waste of resources. An int counting the balance of parenthesis is quite enough:

    int count = 0;
    while (i < s.length()) {
        if (s.charAt(i)==')')
            --count;
        else if (s.charAt(i) = '(')
            count++;
        if (count < 0)
            return false;
    }
    return count == 0;
\$\endgroup\$
  • 1
    \$\begingroup\$ You don't increment i, and you're mixing prefix and postfix inc/decrement. \$\endgroup\$ – Squidly Oct 1 '15 at 13:23
  • \$\begingroup\$ As per your code it will return true for ")(" but this is not balanced string. \$\endgroup\$ – Prashant Apr 8 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.