Δομες Δεδομενων σε JAVA

[pananton]

Καλημερα σε ολους...Θα μπω κατευθειαν στο θεμα...Εχουμε μια εργασια σε java.Αυτο που ζηταει ειναι:

 

Γράψτε ένα πρόγραμμα το οποίο διαβάζει μία παράσταση σε μεταθεματική (postfix)

μορφή από το πληκτρολόγιο και:

 

1. αποθηκεύει την παράσταση σε ένα δυαδικό δένδρο παράστασης, στο οποίο

οι τελεστές είναι εσωτερικοί κόμβοι και οι τελεστέοι είναι φύλλα,

 

2. υπολογίζει την παράγωγό της παράστασης ως προς τη μεταβλητή x

δημιουργώντας ένα νέο δυαδικό δένδρο παράστασης,

 

3. εκτυπώνει την παράγωγο της παράστασης σε μεταθεματική μορφή.

Υποθέστε ότι τα ορίσματα (operands) της μεταθεματικής παράστασης είναι μόνο:

1. η μεταβλητή x,

2. ακέραιες σταθερές χωρίς πρόσημο (π.χ. 1, 2, 14),

3. οι τελεστές +, -, *, /, ^ (ύψωση σε δύναμη).

Σημειώνεται ότι ύψωση σε δύναμη επιτρέπεται μόνο με βάση το x και ακέραιο εκθέτη.

Δίνονται οι ακόλουθοι κανόνες παραγώγισης ως προς τη μεταβλητή x:

1. D(x ^ c) = c * x ^ (c - 1)

2. D(x) = 1

3. D© = 0

4. D(y + z) = D(y) + D(z)

5. D(y - z) = D(y) - D(z)

6. D(y * z) = D(y) * z + y * D(z)

7. D(y / z) = D(y) / z – y / z * D(z) / z

Το c είναι οποιαδήποτε σταθερά, ενώ τα y και z είναι οποιεσδήποτε παραστάσεις.

ΔΟΚΙΜΑΣΤΙΚΑ ΔΕΔΟΜΕΝΑ:

2 x 3 ^ * 2 x * + 5 x / +

ΑΝΑΜΕΝΟΜΕΝΑ ΑΠΟΤΕΛΕΣΜΑΤΑ:

0 x 3 ^ * 2 3 x 2 ^ * * + 0 x * 2 1 * + + 0 x / 5 x / 1 x / * - +

Προσοχή στα ακόλουθα σημεία:

1. Στον κανόνα 1 χρησιμοποιήστε στο δένδρο της παραγώγου απευθείας την

τιμή (c – 1) και όχι την παράσταση (c – 1), έτσι ώστε ο εκθέτης να παραμείνει

ακέραιος και να μπορείτε να επαναλάβετε την παραγώγιση.

2. Στον κανόνα 7 χρησιμοποιήστε στο δένδρο της παραγώγου τη μορφή που

δίνεται, έτσι ώστε να μην εμφανιστούν δυνάμεις με βάση διαφορετική του x

και να μπορείτε να επαναλάβετε την παραγώγιση.

3. Στους κανόνες 6 και 7 όπου η παράγωγος περιέχει τμήματα της αρχικής

παράστασης (τα y και z), να χρησιμοποιήσετε αντίγραφα αυτών των

τμημάτων μέσω της μεθόδου clone().

4. Στους κανόνες 1, 6 και 7 όπου η παράγωγος περιέχει πολλούς τελεστές, ρίζα

του δένδρου της παραγώγου πρέπει να είναι πάντοτε ο τελεστής

χαμηλότερης προτεραιότητας. Στο δεξί τμήμα του κανόνα 7, χρησιμοποιήστε

ως ρίζα το * έτσι ώστε το δένδρο της παραγώγου να είναι ισοζυγισμένο.

Το πρόγραμμά σας θα πρέπει να περιέχει τουλάχιστον τις παρακάτω μεθόδους:

public class DerivativeCalculator {

// tranforms a postfix expression to a binary expression tree

// returns the root of the tree

private static Node createExpressionTree (String expression);

// computes the derivative tree of a binary expression tree

// returns the root of the tree

private static Node createDerivativeTree (Node root);

// converts a binary expression tree to a postfix expression

// returns the expression string

private static String printExpressionTree (Node root);

// tests the methods above

public static void main (String[] args);

}

 

Το αρχείο DerivativeCalculator.java περιέχει τις παραπάνω δηλώσεις καθώς

και ορισμούς για την τάξη Node (ένας κόμβος του δυαδικού δένδρου) και τις

υποτάξεις της VariableNode (κόμβος που περιέχει μεταβλητή), ConstantNode

(κόμβος που περιέχει σταθερά) και OperandNode (κόμβος που περιέχει τελεστή).

Για να διαβάσετε την παράσταση θα χρειαστεί να την αναλύσετε σε λεκτικές μονάδες,

χρησιμοποιώντας την κλάση StreamTokenizer από το πακέτο java.io.

Για να μετατρέψετε την μεταθεματική παράσταση σε δένδρο θα πρέπει να

χρησιμοποιήσετε στοίβα. Ο αλγόριθμος δίνεται παρακάτω. Χρησιμοποιήστε τα

αρχεία Stack.java και ArrayStack.java (υλοποίηση στοίβας με πίνακα) για την

εφαρμογή σας. Μπορείτε να τα τροποποιήσετε αν το κρίνετε απαραίτητο.

Για να υπολογίσετε την παράγωγο του δυαδικού δένδρου παράστασης θα χρειαστεί

να εκτελέσετε μία ενδοδιατεταγμένη διάσχιση του δένδρου δημιουργώντας

παράλληλα το δυαδικό δένδρο παράστασης της παραγώγου, χωρίς να

τροποποιήσετε το αρχικό δένδρο. Ο αλγόριθμος δίνεται παρακάτω.

Για να εκτυπώσετε ένα δυαδικό δένδρο παράστασης σε μεταθεματική μορφή θα

χρειαστεί να εκτελέσετε μία μεταδιατεταγμένη διάσχιση του δένδρου.

 

Στη συνέχεια ακολουθεί περιγραφή των αλγορίθμων μετατροπής μεταθεματικής

παράστασης σε δένδρο και υπολογισμού της παραγώγου.

Αλγόριθμος μετατροπής μεταθεματικής παράστασης σε δένδρο:

• Πραγματοποίησε λεκτική ανάλυση της μεταθεματικής παράστασης.

• Αν η λεκτική μονάδα είναι σταθερά, δημιούργησε έναν ConstantNode με

περιεχόμενο τη σταθερά και push τον κόμβο στη στοίβα.

• Αν η λεκτική μονάδα είναι μεταβλητή, δημιούργησε έναν VariableNode και

push τον κόμβο στη στοίβα.

• Αν η λεκτική μονάδα είναι τελεστής, δημιούργησε έναν OperandNode με

περιεχόμενο τον τελεστή και στη συνέχεια:

o Pop έναν κόμβο από τη στοίβα και θέσε τον ως δεξί παιδί του

OperandNode,

o Pop έναν κόμβο από τη στοίβα και θέσε τον ως αριστερό παιδί του

OperandNode,

o Push τον OperandNode στη στοίβα.

• Επανέλαβε το βήμα αυτό μέχρι να διαβάσεις όλες τις λεκτικές μονάδες.

• Pop τον κόμβο στην κορυφή της στοίβας και επέστρεψέ τον.

Αλγόριθμος παραγώγισης δυαδικού (υπο)δένδρου παράστασης.

• Εξέτασε τον τύπο της ρίζας root του (υπο)δένδρου.

o Αν το root είναι ConstantNode επέστρεψε έναν νέο

ConstantNode με τιμή 0 [κανόνας 3].

o Αν το root είναι VariableNode επέστρεψε έναν νέο

ConstantNode με τιμή 1 [κανόνας 2].

o Αν το root είναι OperandNode επέστρεψε ένα νέο υποδένδρο το

οποίο θα έχει δημιουργηθεί με βάση τον αντίστοιχο κανόνα [κανόνες 1

και 4–7]. Για παράδειγμα, αν ο root περιέχει τον τελεστή +, τότε

δημιούργησε έναν νέο OperandNode, έστω newroot, με τιμή τον

τελεστή + και θέσε newroot.left την παράγωγο του root.left

και newroot.right την παράγωγο του root.right (αναδρομικά).

 

 

 

Κωδικα εχουμε γραψει αλλα μας εμφανιζει μονο την ριζα του δεντρου ή καποιους τελεστες..δηλαδη στην οθονη τυπωνει παντα μονο 1 χαρακτηρα...

Πιστεουμε πως ειναι λαθος H createTree...αν καποιος μπορει να βοηθησει ας πει..

Ευχαριστω για τον χρονο σας