Regex ăn xâu kiểu greedy và lazy

Trong quá trình làm việc với String tôi có gặp một bài toán nhỏ là làm thế nào để loại bỏ hết các xâu con nằm trong dấu đóng mở ngoặc của một xâu bất kỳ VD:

• Công ty (((CT))) trách nhiệm hữu hạn (TNHH) => Công ty trách nhiệm hữu hạn

Điều đầu tiên tôi nghĩ đến là sử dụng regular expression để có thể xử lý ngắn ngọn nhất bài toán này:

String inputString = "Công ty (((CT))) trách nhiệm hữu hạn (TNHH)";
String pattern = "(.*)";
System.out.println("Kết quả: "+inputString.replaceAll(pattern, ""));
Kết quả: Công ty

Tại sao kết quả ko như mong muốn, khi pattern ở trên mới mục đích tìm kiếm tất cả các xâu nằm trong dấu đóng mở ngoặc. Tuy nhiên khi để ý mới thấy rằng xâu đầu vào có rất nhiều dấu mở và đóng ngoặc vậy làm thế nào để pattern trên có thể bắt được vị trí các dấu đóng ngoặc đúng như ý.

Ở pattern trên '*' dùng để chỉ đến số lượng match với ký tự là từ 0 hoặc nhiều, nó sẽ cố gắng match với nhiều ký tự thỏa mãn nhất có thể. Ở ví dụ trên nó sẽ bắt được ký tự "(" đầu tiên và sau đó cố gắng "ăn" xâu đến vị trí và xâu nó "ăn" được là dài nhất, do đó dấu ")" cuối cùng trong xâu sẽ được "ăn". Đó là lý do vì sao sau khi remove xâu trong dấu đóng mở ngoặc đi kết quả trả về chỉ còn lại xâu "Công ty". => Greedy(tham lam) là thuật ngữ để mô tả cách "ăn" xâu của toán tử "*" này.

Như vậy trong trường hợp này không thể sử dụng cách "ăn" xâu greedy này được, vậy trong regex có cách ăn xâu nào khác không? Câu trả lời là có, trái ngược với cách ăn xâu greedy ở trên là cách ăn xâu lazy. Nó sẽ "ăn" xâu ngắn nhất, ngay khi điều kiện match được thỏa mãn. Trong regex dùng toán tử "?" để thể hiện cách "ăn" xâu này. Viết và chạy lại các câu lệnh trên kết quả như sau:

String inputString = "Công ty (((CT))) trách nhiệm hữu hạn (TNHH)";
String pattern = "(.*?)";
System.out.println("Kết quả: "+inputString.replaceAll(pattern, ""));
Kết quả: Công ty )) trách nhiệm hữu hạn

Vẫn không thỏa mãn, vì dùng cách ăn xâu lazy này chỉ bắt được các cặp () không lồng nhau như trong trường hợp dưới

• Công ty (CT) trách nhiệm hữu hạn (TNHH) => Công ty trách nhiệm hữu hạn

Như vậy dùng regex chưa giải quyết được bài toán này, nên tôi phải sử dụng stack để đẩy lần lượt các dấu ')' sau đó cứ bắt gặp vị trí dấu '(' sẽ đánh dấu và xóa xâu string có vị trí lấy từ vị trí này đến vị trí dấu ')' lấy trong stack.pop().

Đây là đoạn mã:

String inputString = Công ty (((CT))) trách nhiệm hữu hạn (TNHH);
System.out.println(removeTextInBracket(inputString));
Kết quả: Công ty  trách nhiệm hữu hạn

// Đẩy các dấu đóng ngoặc vào stack đồng thời remove xâu con khi gặp dấu mở ngoặc
public String removeTextInBracket(String text) {
		int length = text.length();
		int tempLength;
		Stack<Integer> st = new Stack<Integer>();
		for (int i = length-1; i >= 0; i--) {
			if (text.charAt(i) == ')') {
				st.push(i);
				continue;
			}
			if (text.charAt(i) == '(' && !st.isEmpty()) {
				tempLength = text.length();
				text = text.substring(0, i) + text.substring(st.pop() + 1);
				updateStack(st, tempLength - text.length());
			}
		}
		return text;
}

// Update lại vị trí của các dấu đóng mở ngoặc khi độ dài xâu thay đổi.
private static void updateStack(Stack<Integer> stack, int lengthSpan) {
		int size = stack.size();
		Integer temp;
		for (int i = 0; i < size; i++) {
			temp = stack.get(i);
			stack.remove(i);
			stack.add(i, temp - lengthSpan);
		}
}

Đến đây chúng ta đã hiểu hơn về cách ăn xâu "greedy" và "lazy" trong regex.