👨?🏫 平衡括號字符串

給定一個字符串 $s$，該字符串的每個字符都是 (、) 或 # 之一。

你的任務是將 $s$ 中的每個 # 變換為一個或多個 )，從而得到一個平衡括號字符串。

不同 # 變換的 ) 的數量可以不同。

請你輸出為了滿足條件，每個 # 所需變換的 ) 的數量。

如果方案不唯一，則輸出任意合理方案均可。

當一個字符串滿足以下所有條件時，該字符串被稱為平衡括號字符串：

• 字符串僅由 ( 和 ) 組成。
• 字符串所包含的 ( 和 ) 的數量相同。
• 對于字符串的任意前綴，其所包含的 ( 的數量都不少于 ) 的數量。

輸入格式

共一行，一個字符串 $s$。

輸入保證 $s$ 中至少包含一個 #。

輸出格式

如果不存在任何合理方案，則輸出 -1 即可。

如果存在合理方案，則按照從左到右的順序，對于 $s$ 中的每個 #，輸出一行一個正整數，表示該 # 所需變換的 ) 的數量。

如果方案不唯一，則輸出任意合理方案均可。

數據范圍

前 $6$ 個測試點滿足 $1\le |s|\le 20$。
所有測試點滿足 $1\le |s|\le 10^5$。

輸入樣例1：

(((

輸出樣例1：

1
2

輸入樣例2:

()((

輸出樣例2：

2
2
1

---

① 時刻保證字符串前綴的 左括號數 >= 右括號數
② 貪心：在 ① 的基礎上，前邊的 # 都轉換成最少量的 右括號，最后一個 # 轉換成缺失的右括號

---

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;public class Main
{static int N = 100010;static int[] ans = new int[N];// #號轉右括號的個數static int cnt;// 記錄 # 號的個數static boolean solve(String s){char[] cc = s.toCharArray();int t = 0;int len = cc.length;for (int i = 0; i < len; i++){char c = cc[i];if (c == '(')t++;else if (c == ')')t--;else{// #t--;ans[cnt++] = 1;}if (t < 0)// 任何時刻都得保證字符串前綴中的 左括號數 >= 右括號數return false;}ans[cnt - 1] += t;t = 0;for (int i = 0, j = 0; i < len; i++){char c = cc[i];if (c == '(')t++;else if (c == ')'){t--;} else{t -= ans[j++];}if (t < 0)return false;}return true;}public static void main(String[] args){Scanner sc = new Scanner(System.in);String s = sc.next();if (!solve(s))System.out.println(-1);else{for (int i = 0; i < cnt; i++)System.out.println(ans[i]);}}
}