CODEWITHSUNDEEP
javavariablesfor-loopupdates
Daniel Soutar
Daniel Soutar

Reputation: 886

Finding the highest value of a varying number

How do I find the value of a 'high score' of brackets?

private static boolean basicSweep(String input) {
    int noOfClosingParentheses = 0;
    int noOfOpeningParentheses = 0;
    int highScore = 0;
    for (int i = 0; i < input.length(); i++) {
        Character currentCharacter = input.charAt(i);
        if (currentCharacter == '(') {
            noOfOpeningParentheses++;
            highScore++;
        }
        else if (currentCharacter == ')') {
            noOfClosingParentheses++;
        }
    }
    return false;
}

Let's say we have the string "((P)) & (Q v (R & S))". The 'high score', or the maximum in this case would be 2, tied between ((P)) and (...(R&S)). How would I go about doing this? I suspect you store the value in a placeholder variable, but I'm not sure where exactly this variable would go. The current 'highScore' variable is only equal to the total number of opening parentheses, so that's no good.

Any help much appreciated. Apologies for any vagueness - this is quite difficult to explain!

NOTE: the method is a work in progress - no need for any commentary regarding the lack of processing!

EDIT: An attempted answer suggests to set depth and maxDepth variables. Unfortunately, this doesn't work either, under the following implementation:

int depth = 0;
        int maxDepth = 0;
        for (int i = 0; i < input.length(); i++) {
            Character currentCharacter = input.charAt(i);
            if (currentCharacter == '(') {
                noOfOpeningParentheses++;
                depth++;
                maxDepth = depth;
            }
            else if (currentCharacter == ')') {
                noOfClosingParentheses++;
                depth--;
            }
        }
        System.out.println(maxDepth);

maxDepth would be 2 with the string "(((P))) & (P V (Q <-> R))", whereas the actual answer is 3: (((P))).

Upvotes: 0

Views: 57

Answers (3)

aLarsson
aLarsson

Reputation: 91

I would go about this in another direction using a stack. This is based on a simplified version of the http://en.wikipedia.org/wiki/Shunting-yard_algorithm#Detailed_example. But I use only the part about parentheses

private static boolean basicSweep(String input) {
    Stack<String> stack = new Stack<>();
    int value = 0;
    int noOfClosingParentheses = 0;
    int noOfOpeningParentheses = 0;
    int highScore = 0;
    for (int i = 0; i < input.length(); i++) {
        Character currentCharacter = input.charAt(i);
        if (currentCharacter == '(') {
            stack.push("(");//Put a open bracket on the stack
            noOfOpeningParentheses++;
        }
        else if (currentCharacter == ')') {
            while(!stack.isEmpty()){ //
                stack.pop(); //Pop openingparentheses from the stack until none are left 
                value++;//Counting the number of opening parentheses
            }
            highScore = Math.max(highScore, value); //Get the maximum value of our highscore and our maximal value we have found
            value= 0; //Reset counter
            noOfClosingParentheses++;
        }
    }
    return false;
}

Upvotes: 0

akhil gupta
akhil gupta

Reputation: 167

try this code

private static boolean basicSweep(String input) {
int noOfClosingParentheses = 0;
int noOfOpeningParentheses = 0;
int highScore = 0;
for (int i = 0; i < input.length(); i++) {
    Character currentCharacter = input.charAt(i);
    if (currentCharacter == '(') {
        noOfOpeningParentheses++;

    }
    else if (currentCharacter == ')') {
        noOfClosingParentheses++;
         if(noOfOpeningParentheses >= highScore) {
          highScore = noOfOpeningParentheses;
          } 

      noOfOpeningParentheses--;

    }
}
return false;
}

Let me know If this is what you are looking for.

Upvotes: 2

Solomon Slow
Solomon Slow

Reputation: 27115

Start by setting depth=0 and maxDepth=0

Scan the string, increment depth each time the scanner sees an '(', decrement depth each time ')' is seen.

set maxDepth=depth whenever incrementing depth causes it to become greater than maxDepth.

Upvotes: 0

Related Questions