Преобразование префиксного выражения в постфикс - PullRequest
Новая
       21

Преобразование префиксного выражения в постфикс

2 голосов
/ 09 ноября 2010

Я пытаюсь реализовать программу, которая изменяет префиксное выражение на постфиксное, используя рекурсию.

Я написал то, что, как я думал, будет работать, но вместо вывода 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;
            }
        }
    }

1 Ответ

2 голосов
/ 09 ноября 2010

Так что ошибка в вашем коде связана с тем, где вы вычисляете postfix1 и postfix2 - обратите внимание, что вы не компенсируете postfix2.

Чтобы выполнить эту рекурсию, вам нужно разобраться в нескольких случаях:

  • Когда вы сталкиваетесь с оператором, вам нужно выбрать и переместить оператора вправо, а затем обработать любую оставшуюся часть строки, которая не была обработана
  • Когда вы сталкиваетесь с письмом и оператором, вы должны просто вернуть письмо
  • Когда вы встречаете две буквы, вы должны просто вернуть эти две буквы

Это означает, что когда вы сталкиваетесь с чем-то вроде +-abc, вы будете делать следующие шаги: 

f("+-abc") => return f("-abc") + "+" + f(rem1)
 f("-abc") => return f("abc") + "-" + f(rem2)
  f("abc") => return "ab"
  rem2 = "c" (remainder of the string)
  f("c")   => return "c"
 rem1 = ""   (nothing left in the string to parse)

which constructs "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);
    }

}
...