CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 11 of 11
  1. #1
    Join Date
    Aug 2019
    Posts
    3

    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.

  2. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,551

    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++20 Compiler: Microsoft VS2019 (16.11.5)

  3. #3
    Join Date
    Aug 2019
    Posts
    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.

  4. #4
    Arjay's Avatar
    Arjay is offline Moderator / EX MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    13,494

    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.

  5. #5
    Join Date
    Aug 2019
    Posts
    3

    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.

  6. #6
    Arjay's Avatar
    Arjay is offline Moderator / EX MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    13,494

    Re: Program to decompress a compressed string

    Quote Originally Posted by antoniu200 View Post
    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.

  7. #7
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,551

    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!

    Name:  syn_000001.jpg
Views: 2245
Size:  22.6 KB
    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++20 Compiler: Microsoft VS2019 (16.11.5)

  8. #8
    Join Date
    Feb 2017
    Posts
    620

    Re: Program to decompress a compressed string

    Quote Originally Posted by 2kaud View Post
    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.

  9. #9
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,551

    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++20 Compiler: Microsoft VS2019 (16.11.5)

  10. #10
    Join Date
    Feb 2017
    Posts
    620

    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.

  11. #11
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,551

    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++20 Compiler: Microsoft VS2019 (16.11.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
  •  





Click Here to Expand Forum to Full Width

Featured