# präfix zu infix algorithmus



## RoliMG (18. Mai 2008)

hallo liebe java-community!
ich habe aus übung folgendes problem zu lösen:
ich muss einen rekursiven algorithmus entwicklen, der einen präfix-string in infixnotation ausgibt.
dabei soll ein char array verwendet werden und es darf auch ein zweiter hilfsalgorithmus erstellt werden. externe strukturen wie bäume oder stacks dürfen nicht verwendet werden. der präfix-string ist 0 terminiert(zum schluss kommt eine 0)
der algorithmus soll so aussehen:

```
boolean writeInfix(char expr[])
```
der algorithmus gibt zurück ob der string(expression bzw das char array) korrekt ist.
beispiele:
+ab   wird zu    (a+b)
+-abc  wird zu  ((a-b)+c) 
usw.

folgenden ansatz habe ich schon:
ich habe einen zweiten algorithmus definiert, der noch zusätzlich die stringposition übernimmt.

```
public static boolean writeInfix(char expr[]) {
        writeInfix(expr, 0);
        return true;
    }
    
    public static void writeInfix(char expr[], int pos) {
        if(expr[pos] == '0') {
            return;
        }
        
        if(expr[pos] == '+') {
            System.out.print("(");
            writeInfix(expr, pos +1);
            System.out.print(expr[pos]);
        } else {
            System.out.print(expr[pos]);
        }
    }
```
bei diesem ansatz habe ich aber das problem, dass bei dem string "+ab" nur "(a+" ausgegeben wird. ich müsste mir irgendwie merken, wo der algorithmus nach dem + weiterarbeiten soll. habe aber leider keine idee wie das ordentlich auszuprogrammieren ist.
bitte um hilfe!

edit:
sorry!
habe leider erst jetzt gemerkt das der titel des threads "präfix zu infix algorithmus" lauten müsste.

_Edit by Illuvatar: Titel geändert._


----------



## SlaterB (19. Mai 2008)

vor allem wird
+-a..
zu 
(+-..

die Regel muss also sein:
bei +:
(
rekursiver Aufruf 1
+
rekursiver Aufruf 2
)


dieser rekursiver Aufruf ist dann nicht nur ein Zeichen sondern kann beliebig große Strukturen zusammenbauen, 
je nachdem was im String drin ist

du brauchst also auch die Info, wieviele Zeichen 'rekursiver Aufruf 1' liest


----------



## RoliMG (20. Mai 2008)

so weit funktioniert mein algorithmus dank deiner hilfe!
jetzt muss ich aber noch zusätzlich erkennen ob ein ausdruck fehlerhaft eingegeben wurde.
z.b.:
-a
+-ab
etc.
aber wie kann ich das bewerkstelligen?
meinem algorithmus ist ja nur bekannt wann der string zu ende ist, aber nicht, dass er zu früh endet.


----------



## SlaterB (20. Mai 2008)

bei +: 
[Test dass String noch nicht am Ende ist, sonst Fehler]
( 
rekursiver Aufruf 1 
+ 
[Test dass String noch nicht am Ende ist, sonst Fehler]
rekursiver Aufruf 2 
)


----------



## RoliMG (20. Mai 2008)

sorry das ich langsam nerve 
aber:
jetzt habe ich das problem, dass mein algorithmus "+-ab" als fehlerhaft erkennt, aber "+abc" als (a+b) erkennt und sagt es sei richtig. hier der code:

```
static int count = 0;

    public static boolean writeInfix(char expr[], int pos) {
        boolean erg = true;
        
        if (expr[pos] == '0') {
            return false;
        }
        
        count++;

        if (expr[pos] == '+' || expr[pos] == '-' || expr[pos] == '*'
                || expr[pos] == '/') {
            System.out.print("(");
            writeInfix(expr, pos + 1);
            System.out.print(expr[pos]);
            erg = writeInfix(expr, count);
            System.out.print(")");
        } else {
            System.out.print(expr[pos]);
        }

        return erg;
    }
```


----------



## SlaterB (20. Mai 2008)

in der ersten Stufe musst du auslesen, obs am Ende noch weitergeht,
kannst an pos=0 merken, wenn das immer der Fall ist oder in einer zweiten Operation wie am Anfang,

in

```
public class Test
{

    public static void main(String[] args)
        throws Exception
    {
        System.out.println(writeInfix("+".toCharArray(), 0));
    }

    static int count = 0;

    public static boolean writeInfix(char expr[], int pos)
    {
        boolean erg = true;

        if (expr[pos] == '0')
        {
            return false;
        }

        count++;

        if (expr[pos] == '+' || expr[pos] == '-' || expr[pos] == '*' || expr[pos] == '/')
        {
            System.out.print("(");
            writeInfix(expr, pos + 1);
            System.out.print(expr[pos]);
            erg = writeInfix(expr, count);
            System.out.print(")");
        }
        else
        {
            System.out.print(expr[pos]);
        }

        return erg;
    }


}
```
gibts übrigens für "+" eine Exception, falls das so auch dein Programm ist


----------



## RoliMG (20. Mai 2008)

vielen dank für die hilfe!
so funktioniert es:

```
static int count = 0; // gedächtnis für die gelesenen zeichen

    public static boolean writeInfix(char expr[]) {
        boolean erg = writeInfix(expr, 0);

        if (count < expr.length - 1) {
            // kontrollieren ob es nachher noch zeichen gäbe
            erg = false;
        }

        return erg;
    }

    public static boolean writeInfix(char expr[], int pos) {
        boolean erg = true;

        if (expr[pos] == '0') {
            // bis hierher kommt der algo nur bei falschen ausdrücken
            return false;
        }

        count++; // Zeichenzähler

        if (expr[pos] == '+' || expr[pos] == '-' || expr[pos] == '*'
                || expr[pos] == '/') {
            System.out.print("(");
            writeInfix(expr, pos + 1); // linke seite des operators
            System.out.print(expr[pos]);
            erg = writeInfix(expr, count); // rechte seite des operators
            System.out.print(")");
        } else {
            System.out.print(expr[pos]); // ausgabe der konstante
        }

        return erg;
    }
```
 
edit:
dieser code ist für die aufgabenstellung angpasst worden.


----------

