找到一个变化数的最大值

Question

如何找到括号的"高分"值?

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;
}

假设我们有一个字符串"((p)) &Q v (R & p;)"。"高分"，或者在这种情况下的最高分是2分，在((P))和(…(R&S))之间并列。我该怎么做呢?我怀疑您将值存储在占位符变量中，但我不确定该变量将存储在何处。当前的'highScore'变量只等于左括号的总数，所以这是不好的。

非常感谢任何帮助。为任何含糊之处道歉——这很难解释!

注意:该方法是一个正在进行的工作-不需要任何关于缺乏处理的评论!

编辑:尝试回答建议设置深度和maxDepth变量。不幸的是，在以下实现下，这也不起作用:

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值为2，字符串为"((p)) &(P V (Q & lt; -> R))",而实际的答案是3:(((P)))。

Answer 1

试试这个代码

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;
}

让我知道，如果这是你正在寻找的

Answer 2

首先设置depth=0和maxDepth=0

扫描字符串，每次扫描到'('时增加深度，每次看到')'时减少深度。

set maxDepth=depth

Answer 3

我将使用堆栈从另一个方向来解决这个问题。这是基于http://en.wikipedia.org/wiki/Shunting-yard_algorithm#Detailed_example的简化版本。但是我只使用关于括号

的部分

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;
}