Length of longest balanced parentheses prefix using Java

This article explains how to use Java to find the length of the longest balanced parentheses prefix . First, we will understand the problem using several examples and then learn two different approaches to seek it.

Problem explanation

Here we give a string containing parentheses and we need to find the length of the balanced set of parentheses from the string. In other words, if there are all the opening parentheses

"("")", then we call it balanced. prefixes define a balanced set from the beginning of a string. For example, for the set of parentheses '(())()', only '(())' is considered.

Input and output scenarios

For a better understanding, let's take a look at some input and output scenarios.

If the input string is

"(()"
• , the balanced parentheses prefix is ​​(), so the length is 2. If the input string is
"((()()))((("
• , the balanced parentheses prefix is ​​((()())))So the length is 8. If the input string is
"(()())()()"
• , the balanced parentheses prefix is ​​(()()), so The length is 6.
The length of the longest balanced parentheses prefix can be found as follows:

Using stack data structures

• Count opening and closing parentheses
Using stack data structures

Stacks can be used. If you find the opening parentheses '

(

' from the stack, push it onto the stack. If you find a closing parentheses, pop the stack and increment the counter variable by 2 (the balance The length of the pair you got is 2.) Continue doing this and return a counter variable when it becomes an empty stack. Algorithm

The algorithm is as follows:

<code><p><b>ステップ1：</b>スタックとカウンタを初期化します。</p>
<p><b>ステップ2：</b>文字列の各文字を反復処理します。</p></code>

If the character is

(
• , push it onto the stack. If the character is
)
• , pops the stack. Increments the counter by 2.
• Check if the stack is empty.
• If it is empty, ends the loop.

Step 3:

Return the counter at the end.

Example

<code><p><b>ステップ1：</b>スタックとカウンタを初期化します。</p>
<p><b>ステップ2：</b>文字列の各文字を反復処理します。</p></code>

Output

The input string is: ((())(( The length of the longest balanced parentheses prefix is: 6

Count opening and closing parentheses

This approach uses two variables: count and length. If the character is "

(

" from the string, increment count by 1; if the character is ")", decrement count by 1 and increment length by 2 . Check if count is 0, if it is 0, exit the loop and return length. Example

import java.util.Stack;

public class Example {
   public static int longestBalancedPrefix(String s) {
      Stack<Character> stack = new Stack<>();
      int count = 0;
      for (int i = 0; i < s.length(); i++) {
         char c = s.charAt(i);
         if (c == '(') {
            stack.push(c);
         } else if (c == ')') {
            if (!stack.isEmpty()) {
               stack.pop();
               count += 2;
            }
         }
         if (stack.isEmpty()) {
            break;
         }
      }
      return count;
   }

   public static void main(String[] args) {
      String s = "((())(((";
      int length = longestBalancedPrefix(s);
      System.out.println("入力文字列は：" + s);
      System.out.println("最長のバランスの取れた括弧のプレフィックスの長さは：" + length);
   }
}

Output

The input string is ((())())(())) The longest balanced parentheses prefix length is 8

The above is the detailed content of Length of longest balanced parentheses prefix using Java. For more information, please follow other related articles on the PHP Chinese website!