为什么我关于 Bracket Fixing 的代码挂起？

Question

我的代码将带有右括号的表达式的不完整组合")" 转换为带有右括号 "(" 的正确位置的表达式的完整组合。如果右括号和左括号仍然不相等，则使第一个表达式到最后一个优先级，如果仍然不相等，则对第一个索引进行左括号。最多三个表达式（表达式=数字运算符数字）。

示例输入： 4 + 3 ) * 4 - 2 ) * 6 - 6 ) ) )

示例输出： ((4 + 3 ) * ((4 - 2 ) * (6 - 6 ) ) )

我的代码在仅放置 1-2 个右括号时有效。如果超过两个，程序就会挂起。

源代码：

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++;
                }
            }
        }
   
       
    }
}

Answer 1

我认为问题出在你最后的 while 循环上。

问题是您正在运行遍历 Str（您的原始字符串），寻找左括号。但是，您的原始字符串 4 + 3 ) * 4 - 2 ) * 6 - 6 ) ) ) 不包含任何左括号，因此 Str.charAt(j)=='(' 永远不会 true 并且 temp 永远不会递增以匹配 pr。因此条件 temp!=pr 总是 true，因此 while 循环继续执行。

您可能希望将此循环中出现的所有 Str 更改为 Strr，这是您插入左括号的字符串。

然后您将遇到以下行的问题：

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

如果j > 0，这一行将排除Strr中位置j-1的字符。如果 j == 0 这将导致抛出 StringIndexOutOfBoundsException。 .substring 方法的第二个参数不是要包含在子字符串中的最后一个字符的索引，而是该字符之后的下一个字符的索引。 Strr 的子串从头开始，直到但不包括位置 j 的字符，是 Strr.substring(0,j) 而不是 Strr.substring(0,j-1).

另外，为了简单起见，如果希望子串到运行字符串的结尾，可以省略第二个参数。在下面的行中，我对您对 .substring:

的第二次调用进行了修改

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

对您的 class 进行这些更改后，我能够运行它在您的示例输入 4 + 3 ) * 4 - 2 ) * 6 - 6 ) ) ) 上并从中获得输出 ((4 + 3 ) *(( 4 - 2 ) *( 6 - 6 ) ) )。

然而，我运行你的代码在 1 + 5 ) / 4 + 3 ) * 4 - 2 ) * 6 - 6 ) ) ) 上，它再次挂起。

这里的问题是，当您的代码到达 while 循环的顶部时，它将插入四个左括号，还有两个要关闭。然而，通过 for 循环的运行ning 将向 str 添加三个左括号，使 temp 达到 7，而 pr 为 6。7 不会等于 6，因此 while 的主体再次循环运行s，插入更多括号，依此类推，直到字符串变得太大而无法放入内存并且程序崩溃。

最简单的修复方法是将条件 temp<pr 添加到行

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

给你

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

这样你就不会插入太多的左括号。

最后，为了可读性，我强烈建议你给你的变量起一个更具描述性的名字。例如，temp 对于计算到目前为止插入的左括号数量的变量来说不是一个好名字：更好的名字应该是 openParenCount 或者 insertedOpenParensCount。同样，pr 会比 closeParenCount 更好。 Str 可以重命名为 originalString，Strr 可以重命名为 modifiedString。

Answer 2

我不确定您的代码在 while 循环中究竟做了什么，但是我可以确认的一件事是，当输入大于 3 个右括号“)”时，您的代码将进入 while 循环

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++;
            }
        }
    }

此时您的 while 检查 temp!=pr 如果调用此条件是否始终为真，从而创建一个无限循环。

为什么我关于 Bracket Fixing 的代码挂起？

Why does my code about Bracket Fixing hangs?

java

string

search

brackets

java.util.scanner