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.

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.

I do not have access to those test cases. If I did, the problem would have been solved yesterday.

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.

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.

Quote:

---

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.

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! :)

Attachment 35667

Quote:

---

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;

---

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!

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.

Nice! :thumb:

Quote:

---

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.