-
August 17th, 2019, 04:29 AM
#1
Program to decompress a compressed string
Hello! So, I've encountered this problem, on the site I usually work on, that requires me to 'decompress' a 'compressed' string. The code I came up with gives 4 Correct Answers and 6 Wrong Answers. The problem goes like this:
Consider the pattern n[string], which is equivalent to the succession (string) ... (string) ((string) repeated n times). Starting with this model, any string can be compressed.
For example:
- 1[a] is equivalent to a
- 2[ab] is equivalent to abab
- 2[a2[b]] is equivalent to abbabb
- 3[b2[ca]] is equivalent to bcacabcacabcaca
Requirement
Given a compressed string of characters, display its decompression.
Input data
The program reads from the keyboard a correctly compressed stringof characters S.
Output data
The program will display a string of characters that will represent the decompression of the string S.
Restrictions and clarifications
- 3 ≤ the length of the string S ≤ 1000
- decompressed string length ≤ 100,000
- the string S will contain only lowercase letters of the English alphabet
- Time limit: 0.6 seconds
- Memory limit: 64 MB (global) / 8 MB (local)
Example
Input 1
3[a1[b2[c]]]
Output 1
abccabccabcc
Input 2
3[a2[c]]2[x3[y]]
Output 2
accaccaccxyyyxyyy
My code:
Code:
#include <iostream>
#include <string>
#include <cctype>
string input;
int createNumber(int &pos) {
int number = 0;
while (isdigit(input[pos]))
number = number * 10 + input[pos] - '0', input.erase(input.begin() + pos);
return number;
}
string insideParanthesis(int &pos) {
if (input.length()) {
input.erase(input.begin() + pos);
string toRepeat = "";
while (input[pos] != ']') {
while (isalpha(input[pos]) && pos < input.length())
pos++, toRepeat += input[pos - 1];
if (isdigit(input[pos])) {
int timesExpr = createNumber(pos);
int posStart = pos;
timesExpr--;
string expr = insideParanthesis(pos);
if (timesExpr < 0) {
input.erase(input.begin() + posStart, input.begin() + pos);
continue;
}
while (timesExpr--)
input.insert(pos, expr), toRepeat += expr, pos += expr.length();
toRepeat += expr;
}
}
input.erase(input.begin() + pos);
return toRepeat;
}
return "";
}
int main() {
ios_base::sync_with_stdio(false);
getline(cin, input);
for (int i = 0; i < input.length(); i++) {
if (isdigit(input[i])) {
int timesExpr = createNumber(i);
int iStart = i;
timesExpr--;
string expr = insideParanthesis(i);
if (timesExpr < 0 && input.length()) {
input.erase(input.begin() + iStart, input.begin() + i);
continue;
}
else if (!(input.length()))
return 0;
while (timesExpr--)
input.insert(i, expr);
}
}
for (int i = 0; i < input.length(); i++) {
if (input[i] == '[' || input[i] == ']')
continue;
else
cout << input[i];
}
}
I'd like to add that I've seen sumbitted sources on C++ with the same runtime as my source, but with 10 test cases correct out of 10.
If someone has any advice that could help me get those test cases right, I'd be thankful.
-
August 17th, 2019, 05:35 AM
#2
Re: Program to decompress a compressed string
What debugging of the program for the failed cases have you done? This should show where is the issue as execution will deviate from that expected by the design/algorithm.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
August 17th, 2019, 09:05 AM
#3
Re: Program to decompress a compressed string
I do not have access to those test cases. If I did, the problem would have been solved yesterday.
-
August 17th, 2019, 04:26 PM
#4
Re: Program to decompress a compressed string
Add test cases for your code that meet the restrictions and test your code. For example, two requirements are input string <= 1000 and output should be <= 100000 yet you don't have code to test for this.
-
August 17th, 2019, 04:29 PM
#5
Re: Program to decompress a compressed string
Those are the restrictions for the test cases. That means that the program has to use less memory than the specified memory limit, execute faster than the specified max time, while the test cases go up to those given limits. I don't have to test for anything, that's how that Online Judge works.
-
August 17th, 2019, 04:34 PM
#6
Re: Program to decompress a compressed string
Originally Posted by antoniu200
Those are the restrictions for the test cases. That means that the program has to use less memory than the specified memory limit, execute faster than the specified max time, while the test cases go up to those given limits. I don't have to test for anything, that's how that Online Judge works.
Good luck.
-
August 18th, 2019, 07:38 AM
#7
Re: Program to decompress a compressed string
From looking at a quick syntax diagram (see attached).
It looks like a simple LL(1), so I would expect the pseudo-code outline of a program to be something like:
Code:
decomp(...)
{
while (true) {
if letter
process letters
if !number
exit
process number
process [
call decomp
process ]
}
}
main()
{
initialise
call decomp
display result
}
with no real processing code in main(), with it all being being performed in decomp and the associated processing done in that function.
This assumes, of course, that the input is always syntactically correct - which it is for the purpose of this. If the coded program adheres to this design and is shown to work for some cases then by design it should work for all valid cases.
Have fun!
Last edited by 2kaud; August 18th, 2019 at 09:30 AM.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
August 18th, 2019, 03:39 PM
#8
Re: Program to decompress a compressed string
Originally Posted by 2kaud
It looks like a simple LL(1),
Yes the input strings can actually be viewed as programs,
Code:
// input 1: 3[a1[b2[c]]]
for (int i=0; i<3; ++i) {
std::cout << "a";
for (int j=0; j<1; ++j) {
std::cout << "b";
for (int k=0; k<2; ++k) {
std::cout << "c";
}
}
}
std::cout << std::endl;
// input 2: 3[a2[c]]2[x3[y]]
for (int i=0; i<3; ++i) {
std::cout << "a";
for (int j=0; j<2; ++j) {
std::cout << "c";
}
}
for (int i=0; i<2; ++i) {
std::cout << "x";
for (int j=0; j<3; ++j) {
std::cout << "y";
}
}
std::cout << std::endl;
Last edited by wolle; August 18th, 2019 at 04:28 PM.
-
August 19th, 2019, 10:00 AM
#9
Re: Program to decompress a compressed string
From the pseudo-code in post #7, one possible simple program is :
Code:
#include <string>
#include <vector>
#include <iostream>
#include <cctype>
using namespace std;
class Decomp
{
public:
Decomp(const string& s) : str(s), inp(str.c_str()), ch(nextch()) {}
string decomp()
{
vector<string> vs;
while (true) {
if (isalpha(ch)) {
string data;
for (; isalpha(ch); ch = nextch())
data += ch;
vs.push_back(data);
}
if (!isdigit(ch)) {
string ret;
for (const auto& v : vs)
ret += v;
return ret;
}
unsigned int num = 0;
for (; isdigit(ch); ch = nextch())
num = num * 10 + (ch - '0');
ch = nextch(); //get [
const string ret = decomp();
string data1;
while (num--)
data1 += ret;
vs.push_back(data1);
ch = nextch(); //get ]
}
}
private:
char nextch()
{
return *inp++;
}
const string str;
const char* inp = nullptr;
char ch = 0;
};
int main()
{
//const string input = /*"3[a1[b2[c]]]"; // "3[a]";*/ "3[a2[c]]2[x3[y]]";
string input;
getline(cin, input);
Decomp dec(input);
cout << dec.decomp() << endl;
}
Whether this fits the time/memory criteria I haven't tried. It does produce the expected results from the provided examples in post #1. Note that the format of the input is expected to be correct. No format error checks are performed! If the format of the input is not valid, the result is undefined.
Good luck!
Last edited by 2kaud; August 19th, 2019 at 10:48 AM.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
August 19th, 2019, 02:54 PM
#10
Re: Program to decompress a compressed string
Here's a solution that takes the simple structure of the input string into account. The input string is just a hierarchy of r[............] elements.
1. When digits are found r is built until [ is reached. Then r and the current length of the output string l is stored on a stack.
2. When letters are found they're just copied to the output string.
3. When ] is found r and l are popped from the stack. The output string from l to the current end represents the string that got created between the [ and the ]. It is now appended r-1 times to the output (using the copy that's already in the output).
In code it looks like this,
Code:
void test() {
// std::string in = "3[a1[b2[c]]]";
std::string in = "3[a2[c]]2[x3[y]]";
std::stack<int> stack;
std::string out = "";
int n = 0;
for (const auto ch : in) {
if (std::isdigit(ch)) {
n = n*10 + (int(ch) - int('0')); // build the repeats integer
} else if (ch == '[') {
stack.push(n); // number of repeats
n = 0;
stack.push(int(out.size())); // current length of output string
} else if (ch == ']') {
int l = stack.top(); stack.pop();
int r = stack.top(); stack.pop();
while (--r > 0) { // append r-1 copies
const int e = int(out.size());
while (l<e) out += out[l++]; // from l to end of output
}
} else {
out += ch; // must be a letter so just add to output string
}
}
std::cout << out << std::endl;
}
If speed is important it should be hard to beat this. String processing may be slow so it probably is better to use a vector<char> for the output. It's also very space efficient. Apart from the input and output strings there's the just the stack. It's probably impossible to do it with less.
Last edited by wolle; August 19th, 2019 at 06:22 PM.
-
August 20th, 2019, 03:07 AM
#11
Re: Program to decompress a compressed string
Nice!
If speed is important it should be hard to beat this.
You might wring a few more cycles by using stack<pair<int, int>> so you push/pop a pair once rather than 2 push/pop ints.
Last edited by 2kaud; August 20th, 2019 at 09:57 AM.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|