2

再帰を使用して前置式を後置式に変更するプログラムを実装しようとしています。

私はうまくいくと思ったものを書きましたが、代わりab/c*de+f*-に得られる出力のaa/aa/*aa/aa/*-代わりに。

String preの最初の文字を取得しようとしたとき、または の最初の文字を削除しようとしたときに、コードが動かなくなったと思いますString pre。提案/コメントはありますか？

  public class Prefix2Postfix {
        public static final String prefixInput ="-*/abc*+def";
        //desired postfix output is "ab/c*de+f*-"

        public static void main (String[] args){
            System.out.println(pre2Post(prefixInput));
        }

        public static String pre2Post(String pre){
            //find length of string
            int length = pre.length();

            //ch = first character of pre
            char ch = pre.charAt(0);

            //delete first character of pre
            pre = pre.substring(1,length);
            if(Character.isLetter(ch)){
                //base case: single identifier expression
                return (new Character(ch)).toString(ch);
            }else{ 
                //ch is an operator
                String postfix1 = pre2Post(pre);
                String postfix2 = pre2Post(pre);
                return postfix1 + postfix2 + ch;
            }
        }
    }
4

1 に答える 1

2

したがって、コードのエラーは、計算する場所に関係しており、オフセットしていないことpostfix1にpostfix2注意してくださいpostfix2。

この再帰を行うには、いくつかのケースを理解する必要があります:

  • 演算子に遭遇したら、再帰して演算子を右に移動し、処理されていない文字列の残りの部分を処理する必要があります
  • 手紙とオペレーターに遭遇したら、手紙を返すだけです
  • 2文字に遭遇したら、その2文字を返せばいい

これは、次のような+-abcことに遭遇した場合、次の手順を実行することを意味します。

f("+-abc") => return f("-abc") + "+" + f(rem1)
 f("-abc") => return f("abc") + "-" + f(rem2)
  f("abc") => "ab" を返す
  rem2 = "c" (文字列の余り)
  f("c") => "c" を返す
 rem1 = "" (解析する文字列が残っていない)

「ab-c+」を構築する

これはうまくいくはずです：

public static String pre2post(String pre){
    if(pre.length() <= 1){
        return pre;
    }

    if(!Character.isLetter(pre.charAt(0))){
        String a = pre2post(pre.substring(1)) + pre.charAt(0);
        String b = pre2post(pre.substring(a.length()));
        return a + b;
    }else if(!Character.isLetter(pre.charAt(1))){
        return pre.substring(0,1);
    }else{
        return pre.substring(0,2);
    }

}
于 2010-11-09T01:24:57.867 に答える