Avatar billede tosssen Nybegynder
07. maj 2003 - 21:21 Der er 24 kommentarer og
1 løsning

Rekursiv metode

Jeg er ved at løse en opgave, som går ud på at skrive en metode, som finder ud af om en streng følger en bestemt syntaks og returnerer en boolean.

Syntaksen:
Stregen skal enten være "x" eller bestå af to syntaktiskt gyldige strenge adskilt af '+' og omsluttet af parenteser:
Fx:
"x"
"(x+x)"
"((x+x)+x)"

Her er min kode:

public class Testing
{
    public static void main(String[] args)
    {
        if(xsyntaks("(x+x)"))
            System.out.println("Kanon!");
        else
            System.out.println("Lort!");
    }
   
    public static boolean xsyntaks(String str)
    {
        if (str=="x")
        {
            return true;
        }
       
        //Til test af programmet
        System.out.println("x er ikke det samme som "+str);
       
        int plus = str.indexOf('+');
        String s1,s2;
        boolean b1, b2, b3, b4, ok=false;
       
        b1 = str.charAt(0)=='(';
        b2 = str.charAt(str.length()-1)==')';
       
        if (b1 && b2)
        {
            while (plus>=2 && (plus<=str.length()-3) && !ok)
            {
                s1=str.substring(1,plus);
                s2=str.substring(plus+1,str.length()-1);
                b3=xsyntaks(s1);
                b4=xsyntaks(s2);
                ok=(b3 && b4);
                plus = str.indexOf('+', plus+1);
            }
        }
        return ok;
    }
}

Det giver outputtet:

x er ikke det samme som (x+x)
x er ikke det samme som x
x er ikke det samme som x
Lort!

De to midterste linjer forstår jeg ikke! Hvordan kan metoden kaldes med "x" uden at returne true i begyndelsen af koden?
Avatar billede tosssen Nybegynder
07. maj 2003 - 21:24 #1
Doh!! Efter mange timers slid ser jeg nu at jeg ikke har brugt equals i stedet for == til strenge sammenligning ;-)
Avatar billede viciodk Praktikant
07. maj 2003 - 21:25 #2
jep :)
Avatar billede magoo20000 Nybegynder
07. maj 2003 - 21:31 #3
Du kender vel godt forskellen på equals(), logisk lig med og compare() ;-) ?
Avatar billede viciodk Praktikant
07. maj 2003 - 21:35 #4
compare() gør hvad? :)
Avatar billede tosssen Nybegynder
07. maj 2003 - 21:36 #5
== : Dette sammenligner referencer for objekter og værdier for basale typer

equals(): Implementeret i det enkelte objekt med henblik på relevant sammenligning.

compare(): Den må du da gerne klargøre ;-)
Avatar billede tosssen Nybegynder
07. maj 2003 - 21:37 #6
undskyld equals er ikke implementeret i det enkelte objekt, men derimod i den enkelte klasse
Avatar billede codemon Nybegynder
07. maj 2003 - 22:13 #7
== virker også helt fint for strenge - og perfomer hurtigere
Avatar billede tosssen Nybegynder
07. maj 2003 - 22:15 #8
Det er jeg ikke enig i! Ovenstående kode virker jo ikke når jeg bruger ==

Jeg har kun fået det til at virke ved at bruge equals!

Kan du forklare det?
Avatar billede codemon Nybegynder
07. maj 2003 - 22:36 #9
nok lidt for hurtig, JVM laver normalt alias'er af ens strenge. Åbentbart ikke ved rekursive (måske statiske? ) metodekald - ikke altid i hvert fald.

Dit eksempel er det første jeg ser hvor == ikke kan benyttes - hvor der ikke oprettes en streng med new -

Også hedder det sig jo også at man bør bruge equals på strenge, men egentlig tak for et eksempel der viste det, har ledt efter sådan et. (selvom det ikke var det du ville vise :)
Avatar billede tosssen Nybegynder
07. maj 2003 - 22:45 #10
Der kan man bare se hvilke nyttige ting der kommer ud af tilfældige diskusioner her på eksperten ;-)
Avatar billede arne_v Ekspert
07. maj 2003 - 22:55 #11
Du kan godt finde simplere eksempler.

Prøv f.eks.:

public class Equals {
    public static void main(String[] args) {
        String s1 = "ab";
        String s2 = new String("ab");
        String s3 = "a" + "b";
        String s4 = new String("a") + new String("b");
        System.out.println(s1=="ab");
        System.out.println(s2=="ab");
        System.out.println(s3=="ab");
        System.out.println(s4=="ab");
    }
}
Avatar billede codemon Nybegynder
07. maj 2003 - 23:05 #12
ja, men her bruger du new til at oprette en streng. Som jeg sagde - uden new - og det er egentlig også _helt_ forbudt (i hvert fald grimt)
Avatar billede tosssen Nybegynder
07. maj 2003 - 23:06 #13
Nogen der tilfældigvis kan forklare (eller henvise til en forklaring) hvorfor det forholder sig således?
Avatar billede tosssen Nybegynder
07. maj 2003 - 23:08 #14
codemon>> Hvordan ved du om det i mit eksempel ikke skyldes at metoden substring bruger new. Det er jo netop en substring der bliver sendt videre rekursivt.
Avatar billede arne_v Ekspert
07. maj 2003 - 23:09 #15
tossen>

Der er optimizeren der sparer memory ved kun at ligge en konstant i memory
en gange - det har som side effekt at referancerne bliver ens.

Derfor skal man have snydt optimizeren.
Avatar billede arne_v Ekspert
07. maj 2003 - 23:11 #16
codemon>

Så tilføjer vi lige en femte:

public class Equals {
    public static void main(String[] args) {
        String s1 = "ab";
        String s2 = new String("ab");
        String s3 = "a" + "b";
        String s4 = new String("a") + new String("b");
        String s5 = a() + b();
        System.out.println(s1=="ab");
        System.out.println(s2=="ab");
        System.out.println(s3=="ab");
        System.out.println(s4=="ab");
        System.out.println(s5=="ab");
    }
    private static String a() {
        return "a";
    }
    private static String b() {
        return "b";
    }
}
Avatar billede tosssen Nybegynder
07. maj 2003 - 23:20 #17
Lad mig gætte - Dit femte eksempel er således forklaringen på den oprindelige problemstilling i dette spørgsmål?
Avatar billede codemon Nybegynder
07. maj 2003 - 23:24 #18
ok arne_v s5=="ab" havde jeg regnet med at blive true, men den blev false.

tossen, du har ret. Det er netop hvad subString gør, Opretter en ny streng med new.
Avatar billede arne_v Ekspert
07. maj 2003 - 23:24 #19
Det ve djeg ikke.

Men det er et eksempel på problemet uden brug af new.
Avatar billede tosssen Nybegynder
07. maj 2003 - 23:26 #20
Nå, tak for en god diskussion! Jeg har lært noget af det! Godnat ;-)
Avatar billede arne_v Ekspert
07. maj 2003 - 23:26 #21
Jeps.

Optimizeren gennemskuede ikke at de to metoder bare var et par forklædte
konstanter som den kunne have optimeret væk.
Avatar billede arne_v Ekspert
07. maj 2003 - 23:29 #22
tossen>

Iøvrigt - har du overvejet at bruge en parser generator til problemet ?
Avatar billede tosssen Nybegynder
08. maj 2003 - 00:35 #23
Nej det har jeg ikke, fordi jeg må indrømme at jeg ikke ved hvad det er. Fortæl endelig, hvis du gider?
Avatar billede arne_v Ekspert
08. maj 2003 - 08:27 #24
Problemet med manuel parsning som du gør er at der er så meget der skal testes
for.

Prøv f.eks. bare at kør dit program på " (x+x)" !

(et lille skide mellemrum og puf)

Overvej også hvordan din kode ville se ud hvis der skulle tillades:
  - vilkårlige variabel navne (hvor alt undtagen første tegn også kan
    være tal)
  - integer konstanter
  - tilføje -*/

Det vil hurtigt blive rigtigt mange: if && ||.

Løsningen på det er en mere struktureret parser. Enten skrevet
manuelt eller genereret med en parser generator.

Med en parse generator skriver man en grammatik og så genererer
man kode udfra den grammatik til at parse med.

Det har store fordele ved bare lidt mere komplekse ting.

Det bruges meget i C/C++ med yacc/bison (og lex/flex).

Det er ikke helt så udbredt i Java, men der eksisterer faktisk
parser generatorer for Java: JavaCC, CUP (og JLex) og nogle stykker
mere som jeg ike lige kan huske navnene på.

I dit tilfælde vil en grammatik se nogenlunde ud som (skitseret - det
er mig bekendt ikke legal grammatik syntax i nogen specifik
parser generator):

expression :  'x'
            | (expression)
            | expression '+' expression;

Det beskriver hvad den legale syntax er.

Og så sørger parser generatoren for at generere koden.
Avatar billede tosssen Nybegynder
08. maj 2003 - 13:26 #25
Det lyder smart! Jeg vil huske på at der eksisterer sådanne generatorer, når jeg engang skal lave noget mere omfattende. Dette er en programmeringsopgave, som jeg har fået på mit studium, og det ville derfor være snyd at aflevere automatisk genereret kode... Jeg siger dog stadig tak for en brugbar forklaring!
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester