我試圖用 c sharp 撰寫一個函式 complex_decode(string str)，它接受一個非簡單的重復編碼字串，并回傳原始的未編碼字串。例如，“t11h12e14”將回傳“ttttttttttthhhhhhhhhhhheeeeeeeeeeeee”。我已成功解碼長度小于 10 的字串，但無法使用長度超過 10 的字串。我不允許使用正則運算式、庫或回圈。只有遞回。這是我的簡單解碼代碼，當長度小于 10 時解碼。
public string decode(string str)
{
if (str.Length < 1)
return "";
if(str.Length==2)
return repeat_char(str[0], char_to_int(str[1]));
else
return repeat_char(str[0], char_to_int(str[1])) decode(str.Substring(2));
}
public int char_to_int(char c)
{
return (int)(c-48);
}
public string repeat_char(char c, int n)
{
if (n < 1)
return "";
if (n == 1)
return "" c;
else
return c repeat_char(c, n - 1);
}
這按預期作業，例如輸入“a5”回傳“aaaaa”，“t1h1e1”回傳“the”
任何幫助表示贊賞。
uj5u.com熱心網友回復：
這是另一種方法，假設重復字串總是一個字符長并且只使用遞回（和一個StringBuilder物件）：
private static string decode(string value)
{
var position = 0;
var result = decode_char(value, ref position);
return result;
}
private static string decode_char(string value, ref int position)
{
var next = value[position ];
var countBuilder = new StringBuilder();
get_number(value, ref position, countBuilder);
var result = new string(next, Convert.ToInt32(countBuilder.ToString()));
if (position < value.Length)
result = decode_char(value, ref position);
return result;
}
private static void get_number(string value, ref int position, StringBuilder countBuilder)
{
if (position < value.Length && char.IsNumber(value[position]))
{
countBuilder.Append(value[position ]);
get_number(value, ref position, countBuilder);
}
}
uj5u.com熱心網友回復：
我已經重構了你的代碼。我洗掉了 2 個您實際上不需要的不必要的方法。所以，邏輯很簡單，它是這樣作業的；
示例輸入：t3h2e4
- 獲取第一個數字。（這是 2 并且索引為 1）
- 獲取該索引之后的第一個字母，這是我們的下一個字母。（這是“h”，索引為 2）
- 把繩子切開。從索引 1 開始并在索引 2 上結束切片以獲得重復計數。（這是3）
- 重復字串的第一個字母重復計數次數，并將其與從步驟 5 中獲得的結果結合起來。
- 從我們在第二步中獲得的下一個字母索引開始切片到字串的最后，并將其傳遞給遞回方法。
public static string Decode(string input)
{
// If the string is empty or has only 1 character, return the string itself to not proceed.
if (input.Length <= 1)
{
return input;
}
// Convert string into character list.
var characters = new List<char>();
characters.AddRange(input);
var firstDigitIndex = characters.FindIndex(c => char.IsDigit(c)); // Get first digit
var nextLetterIndex = characters.FindIndex(firstDigitIndex, c => char.IsLetter(c)); // Get the next letter after that digit
if (nextLetterIndex == -1)
{
// This has only one reason. Let's say you are in the last recursion and you have c2
// There is no letter after the digit, so the index will -1, which means "not found"
// So, it will raise an exception, since we try to use the -1 in slicing part
// Instead, if it's not found, we set the next letter index to length of the string
// With doing that, you either get repeatCount correctly (since remaining part is only digits)
// or you will get empty string in the next recursion, which will stop the recursion.
nextLetterIndex = input.Length;
}
// Let's say first digit's index is 1 and the next letter's index is 2
// str[2..3] will start to slice the string from index 2 and will stop in index 3
// So, it will basically return us the repeat count.
var repeatCount = int.Parse(input[firstDigitIndex..nextLetterIndex]);
// string(character, repeatCount) constructor will repeat the "character" you passed to it for "repeatCount" times
return new string(input[0], repeatCount) Decode(input[nextLetterIndex..]);
}
例子;
Console.WriteLine(Decode("t1h1e1")); // the
Console.WriteLine(Decode("t2h3e4")); // tthhheeee
Console.WriteLine(Decode("t3h3e3")); // ttthhheee
Console.WriteLine(Decode("t2h10e2")); // tthhhhhhhhhhee
Console.WriteLine(Decode("t2h10e10")); // tthhhhhhhhhheeeeeeeeee
uj5u.com熱心網友回復：
首先你可以簡化你的 repeat_char 函式，你必須有一個明確的停止條件：
public static string repeat_char(char c, int resultLength)
{
if(resultLength < 1) throw new ArgumentOutOfRangeException("resultLength");
if(resultLength == 1) return c.ToString();
return c repeat_char(c, resultLength - 1);
}
請參閱引數的使用相當于回圈上的計數器。所以你可以在主函式上有類似的東西，一個告訴你的子字串何時不再是 int 的引數。
public static string decode(string str, int repeatNumberLength = 1)
{
if(repeatNumberLength < 1) throw new ArgumentOutOfRangeException("length");
//stop condition
if(string.IsNullOrWhiteSpace(str)) return str;
if(repeatNumberLength >= str.Length) repeatNumberLength = str.Length; //Some validation, just to be safe
//keep going until str[1...repeatNumberLength] is not an int
int charLength;
if(repeatNumberLength < str.Length && int.TryParse(str.Substring(1, repeatNumberLength), out charLength))
{
return decode(str, repeatNumberLength 1);
}
repeatNumberLength--;
//Get the repeated Char.
charLength = int.Parse(str.Substring(1, repeatNumberLength));
var repeatedChar = repeat_char(str[0], charLength);
//decode the substring
var decodedSubstring = decode(str.Substring(repeatNumberLength 1));
return repeatedChar decodedSubstring;
}
我使用了默認引數，但您可以輕松地將其更改為更傳統的樣式。這也假設原始 str 的格式正確。
一個很好的練習是更改函式，以便您可以有一個單詞，而不是數字前的字符。然后，例如，您可以將“the3”作為引數（導致“thethe”）。
uj5u.com熱心網友回復：
我采用了更多 Lisp 風格的頭尾方法（如果你說 Lisp，則為 car 和 cdr），并創建了一個類來攜帶當前State的決議狀態。
首先是State班級：
internal class State
{
public State()
{
LastLetter = string.Empty;
CurrentCount = 0;
HasStarted = false;
CurrentValue = string.Empty;
}
public string LastLetter { get; private set; }
public int CurrentCount { get; private set; }
public bool HasStarted { get; private set; }
public string CurrentValue { get; private set; }
public override string ToString()
{
return $"LastLetter: {LastLetter}, CurrentCount: {CurrentCount}, HasStarted: {HasStarted}, CurrentValue: {CurrentValue}";
}
public void AddLetter(string letter)
{
CurrentCount = 0;
LastLetter = letter;
HasStarted = true;
}
public int AddDigit(string digit)
{
if (!HasStarted)
{
throw new InvalidOperationException($"The input must start with a letter, not a digit");
}
if (!int.TryParse(digit, out var num))
{
throw new InvalidOperationException($"Digit passed to {nameof(AddDigit)} ({digit}) is not a number");
}
CurrentCount = CurrentCount * 10 num;
return CurrentCount;
}
public string GetValue()
{
if (string.IsNullOrEmpty(LastLetter))
{
return string.Empty;
}
CurrentValue = new string(LastLetter[0], CurrentCount);
return CurrentValue;
}
}
你會注意到它有一些用于除錯的東西（例如，ToString覆寫和CurrentValue屬性）
一旦你有了它，解碼器就很容易了，它只是在給定的字串上遞回（以及（最初）一個新構造的State實體）：
private string Decode(string input, State state)
{
if (input.Length == 0)
{
_buffer.Append(state.GetValue());
return _buffer.ToString();
}
var head = input[0];
var tail = input.Substring(1);
var headString = head.ToString();
if (char.IsDigit(head))
{
state.AddDigit(headString);
}
else // it's a character
{
_buffer.Append(state.GetValue());
state.AddLetter(headString);
}
Decode(tail, state);
return _buffer.ToString();
}
我在一個簡單的 Windows 表單應用程式中執行此操作，其中有一個用于輸入的文本框、一個用于輸出的標簽和一個用于啟動她的按鈕：
const string NotAllowedPattern = @"[^a-zA-Z0-9]";
private static Regex NotAllowedRegex = new Regex(NotAllowedPattern);
private StringBuilder _buffer = new StringBuilder();
private void button1_Click(object sender, EventArgs e)
{
if (textBox1.Text.Length == 0 || NotAllowedRegex.IsMatch(textBox1.Text))
{
MessageBox.Show(this, "Only Letters and Digits Allowed", "Bad Input", MessageBoxButtons.OK, MessageBoxIcon.Error);
return;
}
label1.Text = string.Empty;
_buffer.Clear();
var result = Decode(textBox1.Text, new State());
label1.Text = result;
}
是的，那里有一個正則運算式，但這只是為了確保輸入有效；它不參與計算輸出。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/527152.html
標籤：C＃递归解码递归数据结构
上一篇：協程的async使用
下一篇：使用遞回找出所有可能的笛卡爾積