有没有比String.Replace更好的方法来从字符串中删除退格键？

Question

我有一个从其他来源读取的字符串，例如"\b\bfoo\bx"。在这种情况下，它将被翻译为单词"fox"，因为前两个\b被忽略，最后的'o'被删除，然后替换为'x'。另一个例子是"patt\b\b\b\b\b\b\b\b\b\bfoo"应该被翻译为"foo"。

我已经使用了String.Replace来解决这个问题，但它很复杂，我担心它不正确，而且它会创建很多新的字符串对象，我想避免这种情况。

有什么想法吗？

- esac

---

你考虑过使用正则表达式吗？ - Jagd

@Jagd 你会推荐哪个正则表达式吗？我正在寻找更优雅的解决方案。几乎任何语言/正则表达式都可以，我特别使用Bash和Ruby来编写我的文本编辑器脚本。 - Brandon

Answer 1

可能最简单的方法就是遍历整个字符串。针对你的输入，以下代码可以在一次遍历中完成操作。

public string ReplaceBackspace(string hasBackspace)
{
    if( string.IsNullOrEmpty(hasBackspace) )
        return hasBackspace;

    StringBuilder result = new StringBuilder(hasBackspace.Length);
    foreach (char c in hasBackspace)
    {
        if (c == '\b')
        {
            if (result.Length > 0)
                result.Length--;
        }
        else
        {
            result.Append(c);
        }
    }
    return result.ToString();
}

- Robert Paulson

---

简单。直接。易于理解。 - Michael Burr

我不知道 Length-- 的技巧，这很棒。我担心 sb.Remove() 会很耗费资源。 - esac

Answer 2

我会采用一种简单易懂的低技术方法。

创建一个字符堆栈。然后从头到尾迭代字符串。如果字符是普通字符（非斜杠），则将其推入堆栈。如果它是一个斜杠，并且下一个字符是'b'，则弹出堆栈顶部。如果堆栈为空，则忽略它。

最后，依次弹出每个字符，将其添加到StringBuilder中，并翻转结果。

- Andrei Krotkov

---

这比我的方法更简洁。+1。 - mqp

很好，虽然我指的是转义字符'\b'，这样我就不需要比较下一个字符是否为'b'，但它仍然有效。看着这个方法，我唯一的“问题”是在方法末尾必须进行Array.Reverse操作..虽然这不是一个昂贵的操作，但我希望能够在不反转的情况下完成 :) - esac

你可以将它们从堆栈中弹出并以相反的顺序放入字符数组中; 即 char [] letters = new char [stack.Count]; for(int i = stack.Count - 1; i >= 0; i--) letters[i] = stack.Pop(); string result = new string(letters); - mqp

Answer 3

public static string ProcessBackspaces(string source)
{
    char[] buffer = new char[source.Length];
    int idx = 0;

    foreach (char c in source)
    {
        if (c != '\b')
        {
            buffer[idx] = c;
            idx++;
        }
        else if (idx > 0)
        {
            idx--;
        }
    }

    return new string(buffer, 0, idx);
}

编辑

我已经对迄今为止在答案中发布的代码进行了快速粗略的基准测试（分别处理问题中的两个示例字符串，每个字符串重复一百万次）：

 ANSWER                 | TIME (ms)
------------------------|-----------
 Luke (this one)        |       318
 Alexander Taran        |       567
 Robert Paulson         |       683
 Markus Nigbur          |      2100
 Kamarey (new version)  |      7075
 Kamarey (old version)  |     30902

- LukeH

---

你的代码很快，但有点不正确。它在测试用例'fox\b\b\b\bfor'中失败了，应该产生"for"（感谢单元测试：）），因为在最后一个\b上idx = 0，所以它将其放入字符缓冲区。这是修复的部分： if (c == '\b') { if (idx > 0) { idx--; } } else { buffer[idx] = c; idx++; } - esac

Luke，这段代码有一个边缘情况的 bug，当有奇数个退格符时，由于“if ((c == '\b') && (idx > 0))”会留下一个初始的 \b 字符，导致它回到了开头。当 idx = 0 时，你正在将 \b 添加到输出中。 - Robert Paulson

请使用我的更新版本更新您的基准测试。在测试时，请将正则表达式的创建移出测试循环，因为每次创建都是不必要的。 - Kamarey

@Kamarey，我已将您的新版本添加到表格中。（今天早上我使用了另一台机器，所以我不得不重新运行和更新所有基准测试，以确保一切保持一致。） - LukeH

Answer 4

正则表达式版本：

var data = @"patt\b\b\b\b\b\b\b\b\b\bfoo";
var regex = new Regex(@"(^|[^\\b])\\b");

while (regex.IsMatch(data))
{
    data = regex.Replace(data, "");
}

---

优化后的版本（适用于退格键 '\b'，而不是字符串 "\b"）：

var data = "patt\b\b\b\b\b\b\b\b\b\bfoo";
var regex = new Regex(@"[^\x08]\x08", RegexOptions.Compiled);

while (data.Contains('\b'))
{
    data = regex.Replace(data.TrimStart('\b'), "");
}

- Kamarey

Answer 5

您可以反向遍历字符串，同时创建一个字符数组。每次遇到一个退格符，就增加一个计数器；每次遇到一个普通字符，如果计数器不为零，则跳过该字符并减少计数器。

我不确定最好的C#数据结构是什么，可以管理它，然后能够快速地按正确的顺序获取字符串。StringBuilder具有Insert方法，但我不知道在开头不断插入字符是否具有性能优势。您可以将字符放在堆栈中，并在最后使用ToArray()方法，这可能会更快，也可能不会更快。

- mqp

Answer 6

String myString = "patt\b\b\b\b\b\b\b\b\b\bfoo";
      List<char> chars = myString.ToCharArray().ToList();
      int delCount = 0;

      for (int i = chars.Count -1; i >= 0; i--)
      {
        if (chars[i] == '\b')
        {
          delCount++;
          chars.RemoveAt(i);
        } else {
          if (delCount > 0 && chars[i] != null) {
            chars.RemoveAt(i);
            delCount--;
          }
        }
      }

- Markus Nigbur

Answer 7

我会这样写： 代码未经测试。

char[] result = new char[input.Length()];
int r =0;
for (i=0; i<input.Length(); i++){
if (input[i] == '\b'  && r>0) r--;
 else result[r]=input[i];

}

string resultsring = result.take(r);

- Alexander Taran

Answer 8

创建一个 StringBuilder，将除了退格字符以外的所有内容复制过去。

- mP.

---

我需要从字符串中删除字符，但仅当存在相应的退格符时才删除，而不仅仅是退格符本身。 - esac