5
\$\begingroup\$

We are given a string which is compressed and we have to decompress it.

(a(bc2)d2)$

"$" indicates end of string.

(abcbcd2)$

abcbcdabcbcd (This is the final uncompressed string.)

My code:

import java.util.*;

class decompress
{
    public static void main(String[] ar)
    {
        int end = 0, st = 0;
        Scanner sc = new Scanner(System.in);
        System.out.print(">> ");
        String s = sc.next();
        while(s.indexOf('(') != -1)
        {
        for(int i = 0; i < s.length(); i++)
        {
            char c = s.charAt(i);
            if(c == '(')
                st = i;
            else if(c == ')')
            {
                end = i;
                String t = s.substring(st+1,end);
                int n = t.charAt(t.length()-1) - '0';
                t = t.substring(0,t.length() - 1);
                String q = "";
                for(int j = 0; j < n; j++)
                    q += t;
                String m = "";
                if(st != 0)
                    m = s.substring(0,st);
                s = m + q + s.substring(i+1);
                break;
            }
        }
        }
        System.out.println(s);
     }
}

Is there a more elegant way to make this program ?

\$\endgroup\$
3
  • \$\begingroup\$ Can you explain a bit about what your code does, how it works? \$\endgroup\$ Dec 19, 2013 at 18:37
  • \$\begingroup\$ @SimonAndréForsberg My code first searches for a string between '()'. Then it replaces that string with the number of times it needs to be. Again the whole process is repeated. \$\endgroup\$ Dec 19, 2013 at 18:40
  • \$\begingroup\$ codereview.stackexchange.com/questions/37769/… \$\endgroup\$
    – Malachi
    Dec 20, 2013 at 19:09

4 Answers 4

10
\$\begingroup\$
  1. Indentation. If you are using Eclipse, please select all your code and press Ctrl + I. Your entire for-loop should be indented one step further.

  2. Use methods. One method for inputting a String, one method for making one iteration of the "decompression".

  3. Did you forget about how to properly use indexOf suddenly? You use indexOf as a condition for your while loop, that makes sense. But then you're using a for-loop to determine the location of the ( and ) characters you are going to work with. This makes no sense to me.

  4. Better variable names. Thanks to your comments on your question, I managed to figure out parts of what you are doing and write a review about that. However, Daniel still has a point that your code is not readable.

  5. Close the scanner. Your scanner is a resource that needs to be closed, call sc.close(); as soon as you are done with the scanner (that is, after you have received all the required inputs from it)

  6. Potential problems. What if I want to encrypt the string (thisWillMessWithYourCode2), how should that string be encrypted in order to be decrypted correctly? Or what would happen if I gave your program the input 42)invalid(data? I believe your code would have a hard time with that.

\$\endgroup\$
1
  • 5
    \$\begingroup\$ +1 for actually reviewing the code. The variables bothered me so powerfully that I felt like it warranted being an answer instead of just a comment. =) \$\endgroup\$
    – Daniel
    Dec 19, 2013 at 19:20
6
\$\begingroup\$

Did you start out code golfing?

Use variable names that mean something. The only variable you used that has any meaning to the reader is end. This means that unless you remember, every time you hit a variable you have to scroll up to find out what it is.

This almost looks obfuscated. (It's not, but it is painful to read.) I'm not even reviewing the logic itself. You need to use meaningful variable names or no one else will ever want to touch your code.

\$\endgroup\$
6
\$\begingroup\$

I have taken a while to answer this question (I started, then work got in the way...). Now that I am back to it, I see that Simon has posted a good review...

So, part 1, a review (and then later, a suggestion):

  • reiterating what Simon and Daniel suggest: the variable names are overly concise, and that is simply unnecessary. sc -> scanner, s -> input, st -> start ... is that too difficult? I can't even guess as to why you chose q though...
  • Your code uses a lot of String concatenation (stringval + someotherstring). This is inefficient. You should have a StringBuilder instance declared at the beginning, and then just copy the data in to the StringBuilder. For example the code:

    for(int j = 0; j < n; j++)
        q += t;
    

    could become:

    StringBuilder decompressed = new StringBuilder(); // declared somewhere at the top
    ....
    for(int j = 0; j < n; j++)
        decompressed.append(t);
    

    if you use decompressed.append(...) then you don't need to keep 'substringing' as well.... i.e. this does not need to be in the loop at all: m = s.substring(0,st);

So, two major issues, variable names, and string concatenation. (in addition to what others have suggested).

Now, for an interesting diversion, consider two alternative methods:

  1. recursion - this problem looks like recursion will be nice.
  2. consider regex - regex to find your 'tokens' will (assuming you understand the regex) make the code short (although exection may be slightly impeded).

Here's a regex method (which is more concise than yours, but probably runs longer):

private static final Pattern TOKEN = Pattern.compile("\\(([^()]+?)(\\d)\\)");

private static String decompress(String input) {
    // check that the last character is '$'.
    if (input.isEmpty() || input.charAt(input.length() - 1) != '$') {
        return input;
    }
    input = input.substring(0, input.length() - 1);

    boolean matched = false;
    do {
        Matcher matcher = TOKEN.matcher(input);
        StringBuffer buffer = new StringBuffer();
        matched = false;
        while (matcher.find()) {
            matched = true;
            matcher.appendReplacement(buffer, "");
            for (int i = (matcher.group(2).charAt(0) - '0') - 1; i >= 0; i--) {
                buffer.append(matcher.group(1));
            }
        }
        matcher.appendTail(buffer);
        input = buffer.toString();
    } while (matched);
    return input;
}
\$\endgroup\$
1
  • \$\begingroup\$ how will we implement recursion ? \$\endgroup\$ Dec 19, 2013 at 19:35
4
\$\begingroup\$

Your question says that $ is some kind of end-of-string marker, yet you treat it just like any other character. I'm not sure why you mentioned $ as a special case.

When doing any non-trivial string manipulation, use a StringBuilder for better performance.

Stuffing all your code into main() is poor programming practice. This code can easily be decomposed into a string-rewriting function and a prompt-and-display driver.

There are several directions you could take to improve the code.

  • Use .lastIndexOf() and .indexOf() to avoid iterating a character at a time.

    public static String shorterDecompress(String s) {
        int openParen;
        StringBuilder sb = new StringBuilder(s);
        while ((openParen = sb.lastIndexOf("(")) >= 0) {
            int closeParen = sb.indexOf(")", openParen);
            int n = sb.charAt(closeParen - 1) - '0';
            String inner = sb.substring(openParen + 1, closeParen - 1);
    
            StringBuilder repeated = new StringBuilder();
            while (n-- > 0) {
                repeated.append(inner);
            }
            sb.replace(openParen, closeParen + 1, repeated.toString());
        }
        return sb.toString();
    }
    
  • Use a stack to store the positions of the open parentheses so that you only have to make one pass through the string.

    public static String stackDecompress(String s) {
        int[] openParens = new int[s.length() / 2];
        int nParens = -1;
    
        StringBuilder sb = new StringBuilder(s);
        for (int i = 0; i < sb.length(); i++) {
            switch (sb.charAt(i)) {
              case '(':
                openParens[++nParens] = i;
                break;
              case ')':
                int n = sb.charAt(i - 1) - '0';
    
                String inner = sb.substring(openParens[nParens] + 1, i - 1);
                StringBuilder repeated = new StringBuilder();
                while (n-- > 0) {
                    repeated.append(inner);
                }
                sb.replace(openParens[nParens--], i + 1, repeated.toString());
    
                // We added repeated.length() characters, but removed (, inner, a digit, and )
                i += repeated.length() - inner.length() - 3;
            }
        }
        return sb.toString();
    }
    
  • Use a regular expression to avoid all tedious drudgery. Unlike the two ideas above and your original code, this should be more resilient to malformed input. Regular expressions also make it easy to support more than one digit for the repeat count. Besides those advantages, the code is very short.

    private static final Pattern PAREN_PATTERN = Pattern.compile("\\(([^(]*?)(\\d*)\\)");
    
    public static String regexDecompress(String s) {
        Matcher m;
        while ((m = PAREN_PATTERN.matcher(s)).find()) {
            String inner = m.group(1);
            try {
                int n = Integer.parseInt(m.group(2));
                inner = new String(new char[n]).replace("\0", inner);
            } catch (NumberFormatException justUseOneOccurrenceThen) {
            }
            s = s.substring(0, m.start()) + inner + s.substring(m.end());
        }
        return s;
    }
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.