# Why does my code about Bracket Fixing hangs?

My code makes an incomplete combination of expressions with closing brackets”)” to a complete combination of expressions with the right placement of Opening Brackets “(“. If closing brackets and opening brackets are still not equal, make the first expressions to the last a priority, if still not equal, make an opening bracket to the first index. Three expressions maximum (expression = digit operator digit).

Sample Input: 4 + 3 ) * 4 – 2 ) * 6 – 6 ) ) )

Sample Output: ((4 + 3 ) * ((4 – 2 ) * (6 – 6 ) ) )

My code works when theres only 1-2 closing brackets placed. if its more than two, the program hangs.

source code:

```import java.util.Scanner;
import java.lang.String;

public class brackets {     //Declaration of Variables
static String Str, Strr="";
static Integer ope=0;
static int temp=0,lent,pr=0,prl=0,prr=0;   //Temp = Opening Brackets placed, lent = string length, pr=Closing Brackets, prl = number of opening brackets made from last index, prr=TBA
static  Scanner scan = new Scanner(System.in);

public static void main(String[]args){

System.out.println("Enter the combined experessions: ");
Str = scan.nextLine();
lent = Str.length();       //Setting the full expression to a string (Str)

for(int i=0; i<lent;i++){        //Finding how many Closing Brackets There are

if(Str.charAt(i)==')'){
pr++;
}

}
Popping(lent);                 //Method
System.out.print(Strr);          //Printing Final Ouput

scan.close();

}

public static void Popping(int lent){

for(int j =lent-1; j>-1;j--){        //I set j to lent because I want to search from rightmost to leftmost
if(Str.charAt(j)==')')          //I need to find a closing bracket first before the program could start to input an opening bracket
prr++;

if(prr>0){
if(Str.charAt(j)=='+'||Str.charAt(j)=='-'||Str.charAt(j)=='*'||Str.charAt(j)=='/'||(j<=lent-2&&Character.isDigit(Str.charAt(j+1))&&Str.charAt(j)==')')){   //Finding an operator or finding a closing bracket which has a digit next to it
ope++;
}
if(ope==2){  //finding two operators mean that I can now put an opening bracket
Strr = '('+Strr;
temp++;
ope=0;
}
}

Strr = Str.charAt(j)+Strr;

if(prr>0){
if(j==0&&temp!=pr){    //If J==0 and Closing brackets still is not equal to Opening Brackets, I'll set opening bracket to the 0 index
Strr = '('+Strr;
temp++;
}
}

}

while(temp!=pr) {   // If still not equal, I'll set an opening bracket to the second opening bracket there is, making the last two expression a priority
for(int j =lent-1; j>-1;j--){
if(Str.charAt(j)=='(')
prl++;
if(prl>1&&Str.charAt(j)=='('){
Strr= Strr.substring(0,j-1)+'('+Strr.substring(j,lent-1);
temp++;
}
}
}

}
}

```

I believe the problem is with your final `while` loop.

The problem is that you are running through `Str` (your original string), looking for opening parentheses. However, your original string `4 + 3 ) * 4 - 2 ) * 6 - 6 ) ) )` does not contain any opening parentheses, so `Str.charAt(j)=='('` is never `true` and `temp` never gets incremented to match `pr`. Hence the condition `temp!=pr` is always `true`, so the `while` loop keeps executing.

You probably want to change all occurrences of `Str` in this loop to `Strr`, which is the string you have been inserting opening parentheses into.

You will then reach a problem with the following line:

```                    Strr= Strr.substring(0,j-1)+'('+Strr.substring(j,lent-1);
```

If `j > 0`, this line will exclude the character at position `j-1` in `Strr`. If `j == 0` this will cause a `StringIndexOutOfBoundsException` to be thrown. The second argument of the `.substring` method isn’t the index of the last character to include in the substring, it’s the index of the next character after that. The substring of `Strr` from the start, up to but not including the character in position `j`, is `Strr.substring(0,j)` instead of `Strr.substring(0,j-1)`.

Also, for simplicity, if you want the substring to run to the end of the string, you can omit the second parameter. In the line below I’ve made this modification to your second call to `.substring`:

```                    Strr= Strr.substring(0,j)+'('+Strr.substring(j);
```

After making these changes to your class, I was able to run it on your sample input `4 + 3 ) * 4 - 2 ) * 6 - 6 ) ) )` and get the output `((4 + 3 ) *(( 4 - 2 ) *( 6 - 6 ) ) )` from it.

However, I then ran your code on `1 + 5 ) / 4 + 3 ) * 4 - 2 ) * 6 - 6 ) ) )`, and it hung once again.

The problem here is that by the time your code reaches the top of your `while` loop, it will have inserted four opening parentheses, leaving two still to be closed. However, running through the `for` loop will add three opening parentheses to `str`, taking `temp` up to 7, when `pr` is 6. 7 does not equal 6, so the body of the `while` loop runs again, inserting more parentheses, and so on and so on, until the string gets too large to fit in memory and the program crashes.

The simplest fix is to add the condition `temp<pr` to the line

```if(prl>1&&Strr.charAt(j)=='('){
```

to give you

```if(prl>1&&Strr.charAt(j)=='('&&temp<pr){
```

That way you don’t end up inserting too many opening parentheses.

Finally, for the sake of readability, I would strongly recommend that you give your variables more descriptive names. For example, `temp` is not a great name for a variable that counts the number of opening parentheses inserted so far: a better name would be `openParenCount` or perhaps `insertedOpenParensCount`. Similarly, `pr` would be better as `closeParenCount`. `Str` could be renamed to `originalString` and `Strr` to `modifiedString`.

5 People found this is helpful