CODEWITHSUNDEEP
javafor-loopjava-8java-stream
Pat
Pat

Reputation: 187

Java 8 rewriting a complex for loop using streams

Is it possible to rewrite a complicated for loop like this just using java 8 streams? Anything I come up with seems more bloated, then just leaving the code as is below with a normal for loop.

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


Using Streams

public static boolean isBalanced2(String text) {
    AtomicInteger count = new AtomicInteger(0);

    text.chars()
        .forEachOrdered(x -> {
             if (x == ')') {
                 count.getAndDecrement();
             } else if (x == '(') {
                 count.getAndIncrement();
             }
        });

    return count.get() == 0;
}

It works ok but it iterates through the whole string, when sometimes that might be wasted computation for example in the case of the string ")......"

It doesn't seem possible to exit the stream as soon as count is < 0 ? (And I dont want to throw an exception!)

Thanks

Upvotes: 3

Views: 452

Answers (6)

Bubletan
Bubletan

Reputation: 3863

Here is a similar solution to yours using Java 8.

First map '(', ')' and other characters to 1, -1 and 0 respectively. Then compute a cumulative sum and check that each partial sum ps >= 0 and the final sum s == 0. By using allMatch for the partial sum checking the process is short-circuiting.

public static boolean isBalanced(String text) {
    AtomicInteger s = new AtomicInteger();
    return text.chars()
            .map(ch -> (ch == '(') ? 1 : (ch == ')') ? -1 : 0)
            .map(s::addAndGet)
            .allMatch(ps -> ps >= 0) && s.get() == 0;
}

Here is a solution that supports multiple different parentheses (requires some IntStack implementation):

IntStack stack = ...;
return text.chars()
        .map("(){}[]"::indexOf)
        .filter(i -> i >= 0)
        .allMatch(i -> {
            int form = i / 2; // 0 = (), 1 = {}, 2 = []
            int side = i % 2; // 0 = left, 1 = right
            if (side == 0) {
                stack.push(form);
                return true;
            } else {
                return stack.size() != 0 && stack.pop() == form;
            }
        }) && stack.size() == 0;

Upvotes: 2

Ousmane D.
Ousmane D.

Reputation: 56423

Firstly, Id like to mention code which involves side-effects typically does not work well with streams for that reason alone I'd suggest proceeding with the imperative approach as:

  1. the code short circuits
  2. it's readable as written

As for:

It works ok but it iterates through the whole string, when sometimes that might be wasted computation for example in the case of the string

Any attempt to short-circuit the stream solution you've shown will involve side-effects and this, in general, is discouraged.

Side-effects in behavioral parameters to stream operations are, in general, discouraged, as they can often lead to unwitting violations of the statelessness requirement, as well as other thread-safety hazards. If the behavioral parameters do have side-effects, unless explicitly stated, there are no guarantees as to the visibility of those side-effects to other threads, nor are there any guarantees that different operations on the "same" element within the same stream pipeline are executed in the same thread.

The conclusion is that streams are not always the solution to all problems rather for specific cases and this case is definitely not stream friendly.

Upvotes: 2

John Bollinger
John Bollinger

Reputation: 180113

You can get early termination of a stream evaluation from one of the terminal operations that supports it. These turn out to be comparatively few, but if you're willing to tolerate some minor abuse, and you're using Java 9 or later, then you can use takeWhile() to perform early termination pretty universally. The trick (and also the abuse) is to use a state-retaining predicate. For example:

public static boolean isBalanced(String text) {
    final int[] state = new int[0];

    text.chars().takeWhile(c -> {
        if (c == '(') state[0]++; if (c == ')') state[0]--; return state[0] >= 0; 
    });

    return state[0] == 0;
}

This is very closely analogous to your original loop.

Upvotes: 0

Andreas
Andreas

Reputation: 159086

The following code will do what you want, and is smaller than your original code, but it's convoluted and always processes all characters, i.e. doesn't stop early if unbalanced ) is detected.

However, unlike some other answers here, it doesn't violate the stream rules by maintaining state outside the stream.

private static boolean isBalanced(String text) {
    return 0 == text.chars()
            .reduce(0, (n, c) -> n < 0 ? n : c == '(' ? n + 1 : c == ')' ? n - 1 : n);
}

The logic is as follows:

  • Keep a running total representing the nesting level, i.e. increment the value when ( is found and decrement the value when ) is found.

  • If the total goes below 0, stop updating it, i.e. when an unbalanced ) is found, keep final total at -1.

The result of the reduce operation is then:

  • 0: All ( have balanced )

  • -1: Found unbalanced )

  • >0: Found unbalanced (

Long version of the same code, using if statements instead of conditional ternary operator.

private static boolean isBalanced(String text) {
    int finalLevel = text.chars().reduce(0, (lvl, ch) -> {
        if (lvl < 0)
            return lvl; // Keep result of -1 for unbalanced ')'
        if (ch == '(')
            return lvl + 1;
        if (ch == ')')
            return lvl - 1;
        return lvl;
    });
    return (finalLevel == 0);
}

Upvotes: 2

NoDataFound
NoDataFound

Reputation: 11949

You should not.

Lambda and Stream are not replacement for all complicated for loop. While you may use a Stream as you've done, this does not means it is better for the eye (what is easier to understand?) and for performance (you surely lost something due to the AtomicInteger vs int based operation but you could probably use a int[] array instead).

  • You can't exit the loop as soon as possible, unless you use exception, but you can narrow your test a little (and you should bench it). You could probably think of using filter after map operation but that won't make it easier to read.
  • You should probably stick to pure function, eg: you should probably not have a side effect (on the AtomicInteger).

Upvotes: 2

Makoto
Makoto

Reputation: 106390

Streams do have the concept of early termination, but only if the terminal operation actually supports it.

From the operation you describe, forEachOrdered is going to iterate over each element in the stream and it does not have the ability to break early. Remember: streams could be infinite, so breaking the stream early while ordering over each one could be seen as a runtime error.

In essence, I'd actually encourage you to stick with the loop variant over the stream variant, since the loop variant gives you the ability to terminate early. What you have written for the stream variant is actually reasonable, given what constraints it has to deal with.

Upvotes: 0

Related Questions