Elearning CodePath – CTP Online Judge

Phát hiện Dấu ngoặc Thừa

RP-Detection

🟢 Easy #General #String

### 📌 Thông tin chung

| Mục | Chi tiết |
| :--- | :--- |
| **Tên File Input** | `ngoac.inp` |
| **Tên File Output** | `ngoac.out` |
| **Độ phức tạp mong muốn** | $O(|S|)$ |

---

### 📝 Bài toán

Cho một biểu thức toán học hợp lệ $S$ không chứa khoảng trắng. Biểu thức $S$ thỏa mãn các điều kiện sau:

1.  Các biến (toán hạng) chỉ là các **chữ cái viết thường** (`a` đến `z`).
2.  Các toán tử chỉ bao gồm: **cộng** (`+`), **trừ** (`-`), **nhân** (`*`), và **chia** (`/`).
3.  Biểu thức $S$ được đảm bảo là **hợp lệ** về mặt cú pháp.

Nhiệm vụ là xác định xem biểu thức $S$ có chứa **dấu ngoặc thừa** (Redundant Parentheses) hay không.

> **Định nghĩa Dấu ngoặc Thừa:** Một cặp dấu ngoặc đơn `( ... )` được coi là thừa nếu việc loại bỏ cặp dấu ngoặc đó không làm thay đổi thứ tự ưu tiên tính toán hoặc giá trị cuối cùng của biểu thức. Điều này xảy ra khi biểu thức con bên trong cặp ngoặc không chứa bất kỳ toán tử nào (chỉ là một biến), hoặc biểu thức con đó đã bị bao quanh bởi các cặp ngoặc khác không cần thiết.

In ra **'Yes'** nếu biểu thức chứa ít nhất một cặp dấu ngoặc thừa, ngược lại in ra **'No'**.

---

### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `ngoac.inp` là một dòng duy nhất chứa chuỗi $S$ – biểu thức toán học.

**Giới hạn (Ràng buộc):**
$$
1 \le |S| \le 10^5
$$
> $|S|$ là độ dài của chuỗi biểu thức $S$.

---

### 📤 Định dạng Đầu ra

Ghi ra file `ngoac.out` kết quả:
* **'Yes'** nếu phát hiện có dấu ngoặc thừa.
* **'No'** nếu không có dấu ngoặc thừa nào.

---

### ✨ Ví dụ

| Input (`ngoac.inp`) | Output (`ngoac.out`) | Giải thích |
| :--- | :--- | :--- |
| `((a+b))` | `Yes` | Biểu thức con `(a+b)` bị bao quanh bởi cặp ngoặc ngoài thừa. |
| `(a+(b)/c)` | `Yes` | Cặp ngoặc bao quanh biến `(b)` là thừa vì `b` không cần ngoặc. |
| `(a+b*c)` | `No` | Không thừa, cần ngoặc nếu muốn thay đổi thứ tự ưu tiên. |
| `(a*(b+c))` | `No` | Cặp `(b+c)` là cần thiết vì ưu tiên nhân cao hơn cộng. |
| `a+(b+c)` | `No` | Không thừa. |
| `a` | `No` | Không có ngoặc nào. |

---

### 💡 Gợi ý thuật toán

Sử dụng cấu trúc dữ liệu **Stack** để giải quyết bài toán với độ phức tạp $O(|S|)$.

1.  Duyệt qua chuỗi $S$. Chỉ xử lý các ký tự: `(`, `)`, toán tử (`+`, `-`, `*`, `/`).
2.  Khi gặp **dấu mở ngoặc** `(` hoặc **toán tử**, đẩy ký tự đó vào Stack.
3.  Khi gặp **dấu đóng ngoặc** `)`:
    * Kiểm tra các phần tử bên trong cặp ngoặc. Nếu phần tử nằm ngay dưới `(` trong Stack là một **toán tử** (tức là có ít nhất một phép tính bên trong), cặp ngoặc đó là **cần thiết**.
    * Nếu ta thấy không có bất kỳ **toán tử** nào giữa `(` và `)` (ví dụ: chuỗi là `(a)` hoặc `((a))` khi đã xử lý các lớp ngoặc ngoài), điều đó chứng tỏ cặp ngoặc này **thừa**.
    * Thực hiện Pop các phần tử cho đến khi gặp dấu mở `(`. Sau đó Pop cả dấu mở `(`.
4.  Nếu trong quá trình Pop sau khi gặp `)`, ta **không tìm thấy** bất kỳ toán tử nào $\rightarrow$ Trả về **'Yes'** (Dấu ngoặc thừa).
5.  Nếu duyệt hết chuỗi mà chưa trả về 'Yes' $\rightarrow$ Trả về **'No'**.

✅ Đã AC: 0 / 0 submissions