Algoritme: polish notation -> infix notation

[armyman]

Hei!

 

Har fått i oppgave å lage et javaprog og asm prog for å konvertere et uttrykk i direct polish notation til infix notation. F eks:

 

The program prints a prompt “>> ”.

• The user types input containing an expression in direct polish. In other words, an operator

precedes its operands. So the direct polish (prefix) expression

= x + * a b / c 3

is equivalent to the infix expression

x = a * b + c / 3

• If end of file is reached (indicated interactively by typing ctrl-D, and getChar returning -1),

the program exits.

• The expression is reprinted as a fully parenthesised infix expression. For example, the

above expression is reprinted as

( x = ( ( a * b ) + ( c / 3 ) ) )

 

Det jeg lurer på er egentlig om noen har noen tips eller anbefalinger til hvordan jeg bør lage denne algoritmen?

 

På forhånd takk!

[MailMan13]

Å overføre fra prefix (polsk) notasjon er relativt enkelt, du trenger en stack og en funksjon som leser og identifiserer et og et symbol og gjør følgende:

 

Når den leser en operator legges den på stakken.

 

Når den leser en operand skrives denne direkte ut og popper den øverste operatoren og skriver denne ut. Dersom det ikke finnes operatorer på stacken er utrykket slutt (Dersom du har korrekt input)

 

I tillegg trenger du å identifisere hvor parantesene skal være for å gi operatorene riktig presedens, det kan gjøres ved at du når du leser en operator vet at her starter et nytt underutrykk så skriver man ut en '(' og legger ')' på stacken. Dersom det ligger ligger en ')' på stakcen når du har skrevet ut en operand vet du at dette er slutten på et underuttrykk og skriver denne ut umiddelbart.

 

Tar forebehold om at dette er tatt på sparket, så det kan være ting som er feil her...

[armyman]

Å overføre fra prefix (polsk) notasjon er relativt enkelt, du trenger en stack og en funksjon som leser og identifiserer et og et symbol og gjør følgende:

 

Når den leser en operator legges den på stakken.

 

Når den leser en operand skrives denne direkte ut og popper den øverste operatoren og skriver denne ut. Dersom det ikke finnes operatorer på stacken er utrykket slutt (Dersom du har korrekt input)

 

I tillegg trenger du å identifisere hvor parantesene skal være for å gi operatorene riktig presedens, det kan gjøres ved at du når du leser en operator vet at her starter et nytt underutrykk så skriver man ut en '(' og legger ')' på stacken. Dersom det ligger ligger en ')' på stakcen når du har skrevet ut en operand vet du at dette er slutten på et underuttrykk og skriver denne ut umiddelbart.

 

Tar forebehold om at dette er tatt på sparket, så det kan være ting som er feil her...

 

Glimrende, akkurat hva jeg trenger men jeg lurer på litt til;

 

Uttrykkene skal lagres og kunne brukes senere ved at man i neste linje f eks legger verdier i a og b, og så får ut et resultat. Kan man gjøre det på en enkel måte dersom man bruker stack?

 

En annen ting, hvordan bruker man stack i Java? Husker jeg gjorde det i assembly ved å skrive push og pop, men aner ikke hvordan man gjør det i Java....

 

Takker for hjelpen så langt!

[MailMan13]

java.util.Stack er en grei en.

 

Da anbefaler jeg at du setter opp en metode som tar input-strengen og deler den opp i operator og operand objekter, da kan du også sette av plass til verdi i operand-objektet og legge disse til i en liste du bruker som symboltabell. Etterhvert som man leser inn verdiene til operandene kan de slås opp i symboltabell og gis riktige verdier. Dette blir det man kaller leksikalsk analyse i kompilator-verdenen (å dele en inputstreng i 'tokens' av riktig type)

 

Skal du beregne svar kan det være lurt å ta vare på prefix-representasjonen, så kan du regne svaret i en løkke i stedet for å måtte finne ut av paranteser og presedens i en eller annen rekursiv greie.

[armyman]

Å overføre fra prefix (polsk) notasjon er relativt enkelt, du trenger en stack og en funksjon som leser og identifiserer et og et symbol og gjør følgende:

 

Når den leser en operator legges den på stakken.

 

Når den leser en operand skrives denne direkte ut og popper den øverste operatoren og skriver denne ut. Dersom det ikke finnes operatorer på stacken er utrykket slutt (Dersom du har korrekt input)

 

I tillegg trenger du å identifisere hvor parantesene skal være for å gi operatorene riktig presedens, det kan gjøres ved at du når du leser en operator vet at her starter et nytt underutrykk så skriver man ut en '(' og legger ')' på stacken. Dersom det ligger ligger en ')' på stakcen når du har skrevet ut en operand vet du at dette er slutten på et underuttrykk og skriver denne ut umiddelbart.

 

Tar forebehold om at dette er tatt på sparket, så det kan være ting som er feil her...

 

Hei igjen!

 

Jeg fant ut det med stack'en (er ikke Java API konge?!).

Jeg sliter med å få til de parantesgreiene da...blir bare surr når jeg setter inn dem...kikk litt på koden og kom gjerne med forslag!

 

Kode (uten parantes-forsøk):

 

import java.io.*;

import java.util.Stack;



public class Test {



   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));



   public static void main(String[] argv) throws Exception{

       new Test();

   }



   public Test() throws Exception{

       System.out.print(">> ");

       String str = in.readLine();

       Stack stakk = new Stack();



       int len = str.length();

    String c;

    for(int i=0;i<len;i++) {

     c = str.substring(i,i+1);

 	if(c.equals("+")) stakk.push(c);

           else if(c.equals("-")) stakk.push(c);

           else if(c.equals("*")) stakk.push(c);

           else if(c.equals("/")) stakk.push(c);

           else if(c.equals("=")) stakk.push(c);

           else if(!stakk.empty() && !c.equals(" ")) System.out.print(c + " " + stakk.pop() + " ");

           else if(!c.equals(" ")) System.out.print(c);

    }

       System.out.println();

   }



}

[MailMan13]

Jeg mener jeg sa det i den første posten.

 

Når du finner en operator vet du at det kommer et underuttrykk, da skriver du ut en '(' og legger ')' på stakken.

 

Når du skriver ut en operand må du sjekke om symbolet du popper er en ')', er den det er det slutt på et underuttrykk og du må poppe og et symbol til, hvis det ikke finnes er du ferdig. Det er bare 3-4 linjer som mangler:

import java.io.*;

import java.util.Stack;



public class Test {



   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));



   public static void main(String[] argv) throws Exception{

       new Test();

   }



   public Test() throws Exception{

       System.out.print(">> ");

       String str = in.readLine();

       Stack stakk = new Stack();



       int len = str.length();

      String c;

      for(int i=0;i<len;i++) {

         c = str.substring(i,i+1);

        if(c.equals("+") || c.equals("-") || c.equals("*") || c.equals("/") || c.equals("=")) {

         System.out.print('(');

         stakk.push(")");

         stakk.push(c);

  }

           else if(!stakk.empty() && !c.equals(" ")) {

           	String s = (String)stakk.pop();

           	System.out.print(c + " " +  s + " ");

   if(s.equals(")") && !stakk.empty())

   	System.out.print(stakk.pop());



 	}

           else if(!c.equals(" ")) System.out.print(c);

      }

       System.out.println();

   }

[armyman]

Jeg mener jeg sa det i den første posten.

 

Når du finner en operator vet du at det kommer et underuttrykk, da skriver du ut en '(' og legger ')' på stakken.

 

Når du skriver ut en operand må du sjekke om symbolet du popper er en ')', er den det er det slutt på et underuttrykk og du må poppe og et symbol til, hvis det ikke finnes er du ferdig. Det er bare 3-4 linjer som mangler

 

Se der ja nå begynner det å ligne på noe! Takker for hjelpen med det. Nå lurer jeg imidlertid litt på en viktig ting videre i oppgaven og det gjelder utregning av resultatet. Oppgaven sier at dersom det ikke er gitt noen verdier til variablene (som er en liten bokstav fra a til z), så kan de antas å være 0. Det jeg lurer på er hvordan jeg kan legge til verdier til f eks a eller b eller hva det nå er bruker taster inn.

 

Hvis jeg antar at bruker legger inn uttrykket = a 2, så skal jo en integer i programmet ved navn a settes lik 2. Jeg tenkte at det var mest hensiktsmessig å ha en array fremfor 26 variabler, men hvordan kan jeg lettest referere til a da? Man må jo bruke array[index] og da vil det jo bli noe sånt som array[0] for a og array[1] for b osv...det er jo litt tungvint da jeg må lage en link fra hver bokstav og til riktig index i array'en også....

 

Vet du om det finnes en bedre måte å gjøre dette på?

 

mvh

Ex-Armyman, nå student.

[tmx]

Bruk en hashtable (java.util.Hashtable), da kan du bruke hva som helst som key:

 

hashtable = new Hashtable();

 

hashtable.put("a", verdi);