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++;
}
}
}
}
}
Advertisement
Answer
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.