Custom-Encoded String Decode

Implement decode_feed(encoded), which decodes a string in a vendor's run-length scheme and returns the decoded string.

A legacy market data vendor compresses its symbol directory with a custom run-length scheme. The spec, recovered from a fax, is short but exact.

An encoded string is a sequence of tokens with no separators. There are two token kinds:

• Repeat token: one or more digits, then ~, then one or more lowercase letters. The letter run extends until the next digit, the next ^, or the end of the input. The token emits the letter run repeated count times: 3~ab emits ababab.
• Shift token: ^ followed by exactly one digit 1-9. It emits a copy of the previous token's entire emission with every letter shifted forward in the alphabet by that digit, wrapping z back to a: after 3~ab emitted ababab, the token ^2 emits cdcdcd. "Entire emission" means everything that one token emitted, the whole repeated block, not the whole decoded output so far. The shifted copy becomes the new "previous emission", so shift tokens chain: each one shifts what the token immediately before it emitted. In 2~ab^1^1, the first ^1 emits bcbc and the second ^1 emits cdcd.

The decoded output is the concatenation of every token's emission, in order. The input is always valid: it starts with a repeat token, counts are at least 1, and letter runs are non-empty.

std::string decode_feed(const std::string& encoded);

The encoded stream comes in as a std::string and the decoded output goes back as one.

Examples

decode_feed("3~ab");
// "ababab"  (repeat "ab" three times)

decode_feed("2~ab^1");
// "ababbcbc"  ("abab", then "abab" shifted by 1)

decode_feed("2~ab^1^1");
// "ababbcbccdcd"  ("abab", then "bcbc", then "bcbc" shifted by 1)

decode_feed("1~zq2~x");
// "zqxx"  (letters end where the next count starts)

Constraints

• Encoded length up to \(10^4\); counts can be multi-digit (for example 12~q); decoded output stays under \(10^6\) characters.
• Only lowercase letters appear in runs; shifts wrap z to a.
• No cleverness required on speed, but your tokenizer must be exact: every hidden test is an edge of the grammar, not a bigger version of the examples.