题解 | #小苯的IDE括号问题（easy）#

题目链接

题目描述

给定一个包含 (, ) 和一个光标 I 的字符串，以及一个操作序列。需要模拟两种删除操作并输出最终的字符串。

backspace:
1. 如果光标左边是 (，右边是 )，则同时删除这对括号。
2. 否则，如果光标左边有字符，只删除左边的一个字符。
3. 如果左边没字符，则无操作。
delete:
1. 如果光标右边有字符，删除右边的一个字符。
2. 如果右边没字符，则无操作。

解题思路

直接在字符串上进行删除操作效率很低，因为每次删除都可能导致大量字符的移动。为了高效地模拟光标左右两侧的删除操作，我们可以使用一个经典的数据结构技巧：两个栈（或双端队列）。

一个栈 $left\_part$ 用于存储光标左边的所有字符。
另一个栈 $right\_part$ 用于存储光标右边的所有字符。

为了方便操作，我们让 $left\_part$ 的栈顶是离光标最近的字符，而 $right\_part$ 的栈顶也是离光标最近的字符。这意味着， $left\_part$ 正常存储（字符串 abc 存为 a,b,c），而 $right\_part$ 需要反向存储（字符串 def 存为 f,e,d）。

算法步骤如下：

初始化：
- 找到光标 I 的位置。
- 将光标左边的字符依次压入 $left\_part$ 栈。
- 将光标右边的字符从右到左依次压入 $right\_part$ 栈。
模拟操作：
- 遍历操作序列，对于每个操作：
- backspace:
  - 首先检查特殊情况： $left\_part$ 和 $right\_part$ 都不为空，且 $left\_part$ 的栈顶是 (， $right\_part$ 的栈顶是 )。如果满足，则分别从两个栈中弹出一个元素。
  - 如果不满足特殊情况，且 $left\_part$ 不为空，则只从 $left\_part$ 中弹出一个元素。
- delete:
  - 如果 $right\_part$ 不为空，则从 $right\_part$ 中弹出一个元素。
输出结果：
- 所有操作完成后，最终的字符串由三部分拼接而成：
  1. $left\_part$ 中的所有字符（需要按顺序读出，不能直接 $pop$ ）。
  2. 光标 I。
  3. $right\_part$ 中的所有字符（需要反向读出，即依次 $pop$ ）。

使用两个栈（或 Python 中的列表，Java 中的 ArrayDeque）可以将每次操作的时间复杂度降至均摊 $O(1)$ 。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;

    deque<char> left_part;
    deque<char> right_part;

    size_t cursor_pos = s.find('I');
    for (size_t i = 0; i < cursor_pos; ++i) {
        left_part.push_back(s[i]);
    }
    for (size_t i = n - 1; i > cursor_pos; --i) {
        right_part.push_back(s[i]);
    }

    for (int i = 0; i < q; ++i) {
        string op;
        cin >> op;
        if (op == "backspace") {
            if (!left_part.empty() && !right_part.empty() && left_part.back() == '(' && right_part.back() == ')') {
                left_part.pop_back();
                right_part.pop_back();
            } else if (!left_part.empty()) {
                left_part.pop_back();
            }
        } else { // delete
            if (!right_part.empty()) {
                right_part.pop_back();
            }
        }
    }

    for (char c : left_part) {
        cout << c;
    }
    cout << 'I';
    while (!right_part.empty()) {
        cout << right_part.back();
        right_part.pop_back();
    }
    cout << endl;

    return 0;
}

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        String s = sc.next();

        Deque<Character> leftPart = new ArrayDeque<>();
        Deque<Character> rightPart = new ArrayDeque<>();

        int cursorPos = s.indexOf('I');
        for (int i = 0; i < cursorPos; i++) {
            leftPart.addLast(s.charAt(i));
        }
        for (int i = n - 1; i > cursorPos; i--) {
            rightPart.addLast(s.charAt(i));
        }

        for (int i = 0; i < q; i++) {
            String op = sc.next();
            if (op.equals("backspace")) {
                if (!leftPart.isEmpty() && !rightPart.isEmpty() &&
                    leftPart.peekLast() == '(' && rightPart.peekLast() == ')') {
                    leftPart.pollLast();
                    rightPart.pollLast();
                } else if (!leftPart.isEmpty()) {
                    leftPart.pollLast();
                }
            } else { // delete
                if (!rightPart.isEmpty()) {
                    rightPart.pollLast();
                }
            }
        }

        StringBuilder result = new StringBuilder();
        for (char c : leftPart) {
            result.append(c);
        }
        result.append('I');
        while (!rightPart.isEmpty()) {
            result.append(rightPart.pollLast());
        }
        System.out.println(result.toString());
    }
}

n, q = map(int, input().split())
s = input()

cursor_pos = s.find('I')
left_part = list(s[:cursor_pos])
right_part = list(s[cursor_pos + 1:])
right_part.reverse()

for _ in range(q):
    op = input()
    if op == "backspace":
        if left_part and right_part and left_part[-1] == '(' and right_part[-1] == ')':
            left_part.pop()
            right_part.pop()
        elif left_part:
            left_part.pop()
    else:  # delete
        if right_part:
            right_part.pop()

right_part.reverse()
result = "".join(left_part) + 'I' + "".join(right_part)
print(result)

算法及复杂度

算法：双栈（或双端队列）模拟。
时间复杂度： $O(n+q)$ ，其中 $n$ 是初始字符串长度， $q$ 是操作次数。初始化需要 $O(n)$ ，每次操作的复杂度是 $O(1)$ 。
空间复杂度： $O(n)$ ，用于存储两个栈中的字符。