Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I wrote this program to match square brackets as part of a Brainf**k interpreter. I'm aware that it gets caught in an infinite loop if brackets are entered like this: ][.

  1. Are there any performance improvements I can make?
  2. Should I change any variable names?
  3. Are there other syntax errors that will break the code?
  4. How can I fix said errors?
  5. Anything else I did wrong?

//Matches an opening or closing bracket to a corresponding opening or closing bracket
int getMatchingBraceIndex(unsigned int braceIndex, char* str) {
    //Current nesting level
    int level = 0;
    //Matching brace's nesting level
    //(Matching braces have to be at the same level)
    int returnLvl = -1;

    /*******************************************************************************\
     * Note:                                                                       *
     * If brace given is open brace, iterate through string from beginning to end  *
     * If brace given is close brace, iterate through string from end to beginning *
    \*******************************************************************************/
    //If brace given is open brace
    if (str[braceIndex] == '[') {
        //Iterator
        int i = 0;

        //Iterate through given string
        for (i; i < strlen(str); i++) {
            //If current character of string is open brace
            if (str[i] == '[') {
                //Increment nesting level
                level++;
                //If current character is given brace, assume that matching brace is on the same nesting level
                if (i == braceIndex) {
                    returnLvl = level;
                }
            //If current character of string is close brace
            } else if (str[i] == ']') {
                //If currnet nesting level is nesting level of matching brace, return current index
                if (level == returnLvl) {
                    return i;
                //Otherwise, decrement nesting level and keep going through the string
                } else {
                    level--;
                }
            }
        }
    //If brace given is close brace
    } else if (str[braceIndex] == ']') {
        //Iterator
        int i = strlen(str) - 1;

        //Iterate through given string
        for (i; i >= 0; i--) {
            //If current character of string is close brace
            if (str[i] == ']') {
                //Increment nesting level
                level++;
                //If current character is given brace, assume that matching brace is on the same nesting level
                if (i == braceIndex) {
                    returnLvl = level;
                }
            //If current character of string is open brace
            } else if (str[i] == '[') {
                //If nesting level is nesting level of matching brace, return current index
                if (level == returnLvl) {
                    return i;
                //Otherwise, decrement nesting level and keep going through the string
                } else {
                    level--;
                }
            }
        }
    } else {
        //Error
        setColor(RED, BLACK);
        printf("Unable to match brace at index %i\n", braceIndex);
        setColor(DEFAULT, BLACK);
        return -1;
    }

    return -1;
}
share|improve this question
1  
I would not scan backwards for the open brace. When you hit an open brace push the current position onto the stack. When you hit a close brace pop the value and just move the instruction pointer to that location. –  Loki Astari Apr 26 at 8:56
add comment

3 Answers 3

Do not use strlen() in for loops. strlen() walks over the string every time you call it.

share|improve this answer
    
So I should assign it to a variable at the start and then access the variable? –  FracturedRetina Apr 26 at 3:42
    
yes. You should definitely do that. –  Himanshu Apr 27 at 1:04
add comment

The outer if/else if blocks have a lot of duplicate code. This should be put into a separate function to be called by both conditionals and given the relevant arguments.

This will also make it easier to determine if that code itself should be refactored because you'll just have one occurrence of it. Overall, putting duplicate code into a separate function helps with maintainability, readability, and DRY (Don't Repeat Yourself).

share|improve this answer
add comment

You have way to many comments.

            //Increment nesting level
            level++;

Thanks. But I can read the code. I don't need a comment to tell me that.
Too many comments is a real problem. Because the code can become out of sync with the comments then what does the maintainer do? Does he believe the comments and fix the code to make them align with the comments. What happens if the code was changed because there was a subtle bug?

Reserve comments to describe what you are trying to achieve. NOT how you are achieving it (the code is a description of how). The comments should by WHY (and potentially the goal).

Why is this in the middle of the loop?

           if (i == braceIndex) {
                returnLvl = level;
            }

This is the start condition.
OK. I see its because you start scanning from the start of the string.

for (i; i < strlen(str); i++) { 
   // Real performance hit if `braceIndex` is 10,000,000
   // You are scanning the program you just executed.
   // You only need to find the closing brace.

Why not start scanning from the position of the brace

int strend = strlen(str);
returnLvl = 1; // start after the opening '['

// When returnLvl gets back to 0 you can exit
for (i = braceIndex + 1; i < strend && returnLvl > 0; ++i) {

Then what the other two said.

The last thing is you don't need to scan backwards.
As you hit an open brace push the current instruction pointer value onto a stack. As you hit a close pop the value. If the condition is correct reset the instruction pointer to the stored value.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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