Πώς να δημιουργήσετε ένα tokenizer έκφρασης μαθηματικών χρησιμοποιώντας JavaScript (ή οποιαδήποτε άλλη γλώσσα)

Πριν από λίγο καιρό, εμπνεύστηκα να δημιουργήσω μια εφαρμογή για την επίλυση συγκεκριμένων ειδών μαθηματικών προβλημάτων. Ανακάλυψα ότι έπρεπε να αναλύσω την έκφραση σε ένα αφηρημένο συντακτικό δέντρο, οπότε αποφάσισα να δημιουργήσω ένα πρωτότυπο στο Javascript. Ενώ εργαζόμουν στο πρόγραμμα ανάλυσης, συνειδητοποίησα ότι το tokenizer έπρεπε να χτιστεί πρώτα. Θα σας καθοδηγήσω πώς να κάνετε ένα μόνοι σας. (Προειδοποίηση: είναι πιο εύκολο από ό, τι φαίνεται στην αρχή.)

Τι είναι το Tokenizer;

Το tokenizer είναι ένα πρόγραμμα που χωρίζει μια έκφραση σε ενότητες που ονομάζονται tokens . Για παράδειγμα, εάν έχουμε μια έκφραση όπως "Είμαι ένας μεγάλος προγραμματιστής λίπους", θα μπορούσαμε να το αντιστοιχίσουμε με διαφορετικούς τρόπους, όπως:

Χρησιμοποιώντας λέξεις ως μάρκες,

0 => I’m1 => a2 => big3 => fat4 => developer

Χρησιμοποιώντας χαρακτήρες χωρίς κενό διάστημα ως διακριτικά,

0 => I1 => ‘2 => m3 => a4 => b…16 => p17 => e18 => r

Θα μπορούσαμε επίσης να θεωρήσουμε όλους τους χαρακτήρες ως διακριτικά

0 => I1 => ‘2 => m3 => (space)4 => a5 => (space)6 => b…20 => p21 => e22 => r

Έχεις την ιδέα, σωστά;

Το Tokenizer (ονομάζεται επίσης lexers) χρησιμοποιείται για την ανάπτυξη μεταγλωττιστών για γλώσσες προγραμματισμού. Βοηθούν τον μεταγλωττιστή να έχει δομική λογική από αυτά που προσπαθείτε να πείτε. Σε αυτήν την περίπτωση, ωστόσο, χτίζουμε ένα για μαθηματικές εκφράσεις.

Διακριτικά

Μια έγκυρη μαθηματική έκφραση αποτελείται από μαθηματικά έγκυρα διακριτικά, τα οποία για τους σκοπούς αυτού του έργου θα μπορούσαν να είναι Literals , Variables , Operators, Functions or Function Argument Separators .

Μερικές σημειώσεις για τα παραπάνω:

  • Το Literal είναι ένα φανταχτερό όνομα για έναν αριθμό (σε αυτήν την περίπτωση). Θα επιτρέπουμε μόνο αριθμούς σε ολόκληρη ή δεκαδική μορφή.
  • Μια μεταβλητή είναι το είδος που έχετε συνηθίσει στα μαθηματικά: a, b, c, x, y, z. Για αυτό το έργο, όλες οι μεταβλητές περιορίζονται σε ονόματα ενός γράμματος (οπότε τίποτα δεν είναι όπως το var1 ή η τιμή ). Αυτό είναι έτσι ώστε να μπορούμε να συμβολίσουμε μια έκφραση όπως το ma ως προϊόν των μεταβλητών m και a , και όχι μία μεμονωμένη μεταβλητή ma .
  • Οι χειριστές ενεργούν για τα λογικά και τις μεταβλητές και τα αποτελέσματα των συναρτήσεων. Θα επιτρέψουμε στους τελεστές +, -, *, / και ^.
  • Οι λειτουργίες είναι «πιο προηγμένες» λειτουργίες. Περιλαμβάνουν πράγματα όπως sin (), cos (), tan (), min (), max () κ.λπ.
  • Το Function Argument Separator είναι απλώς ένα φανταχτερό όνομα για κόμμα, που χρησιμοποιείται σε ένα πλαίσιο όπως αυτό: max (4, 5) (το μέγιστο μία από τις δύο τιμές). Το αποκαλούμε Function Argument Separator, διότι, διαχωρίζει τα ορίσματα συνάρτησης (για συναρτήσεις που απαιτούν δύο ή περισσότερα ορίσματα, όπως max και min ).

Θα προσθέσουμε επίσης δύο διακριτικά που συνήθως δεν θεωρούνται διακριτικά, αλλά θα μας βοηθήσουν με σαφήνεια: Αριστερή και Δεξιά παρένθεση . Ξέρεις τι είναι.

Λίγες εκτιμήσεις

Σιωπηρός πολλαπλασιασμός

Σιωπηρή πολλαπλασιασμού σημαίνει απλά επιτρέποντας στο χρήστη να γράψει «στενογραφία» πολλαπλασιασμούς, όπως , αντί της 5 * x . Κάνοντας ένα βήμα παραπέρα, επιτρέπει επίσης να το κάνετε με λειτουργίες ( 5sin (x) = 5 * sin (x) ).

Ακόμα πιο μακριά, επιτρέπει 5 (x) και 5 (sin (x)). Έχουμε την επιλογή να το επιτρέψουμε ή όχι. Ανταλλάξεις; Αν δεν το επιτρέψατε, θα διευκόλυνε το tokenizing και θα επέτρεπε τη μεταβλητή ονομάτων πολλαπλών γραμμάτων (ονόματα όπως price). Επιτρέποντάς το να κάνει την πλατφόρμα πιο διαισθητική για τον χρήστη, και, επίσης, παρέχει μια πρόσθετη πρόκληση που πρέπει να ξεπεραστεί. Επέλεξα να το επιτρέψω.

Σύνταξη

Ενώ δεν δημιουργούμε μια γλώσσα προγραμματισμού, πρέπει να έχουμε κάποιους κανόνες σχετικά με το τι κάνει μια έγκυρη έκφραση, έτσι ώστε οι χρήστες να γνωρίζουν τι να εισαγάγουν και ξέρουμε τι να σχεδιάσουμε. Με ακριβείς όρους, τα διακριτικά μαθηματικών πρέπει να συνδυάζονται σύμφωνα με αυτούς τους κανόνες σύνταξης για να είναι έγκυρη η έκφραση. Εδώ είναι οι κανόνες μου:

  1. Τα διακριτικά μπορούν να διαχωριστούν με 0 ή περισσότερους χαρακτήρες στο κενό διάστημα
2+3, 2 +3, 2 + 3, 2 + 3 are all OK 5 x - 22, 5x-22, 5x- 22 are all OK

Με άλλα λόγια, το διάστημα δεν έχει σημασία (εκτός από ένα διακριτικό πολλαπλών χαρακτήρων όπως το Literal 22).

2. Τα επιχειρήματα συναρτήσεων πρέπει να είναι σε παρένθεση ( sin (y) , cos (45) , όχι sin y , cos 45 ). (Γιατί; Θα αφαιρούμε όλα τα κενά από τη συμβολοσειρά, οπότε θέλουμε να μάθουμε από πού ξεκινά και τελειώνει μια λειτουργία χωρίς να χρειάζεται να κάνουμε κάποια «γυμναστική».)

3. Ο έμμεσος πολλαπλασιασμός επιτρέπεται μόνο μεταξύ Literals και Variables , ή Literals and Functions , με αυτήν τη σειρά (δηλαδή, τα Literals έρχονται πάντα πρώτα) και μπορεί να είναι με ή χωρίς παρενθέσεις. Αυτό σημαίνει:

  • ένα (4) θα αντιμετωπίζεται ως κλήση συνάρτησης και όχι ως * 4
  • Το a4 δεν επιτρέπεται
  • και 4 (α) είναι εντάξει

Τώρα, ας πάμε στη δουλειά.

Μοντελοποίηση δεδομένων

Σας βοηθά να έχετε ένα δείγμα στο κεφάλι σας για να το δοκιμάσετε. Θα ξεκινήσουμε με κάτι βασικό: 2y + 1

Αυτό που περιμένουμε είναι ένας πίνακας που παραθέτει τα διαφορετικά διακριτικά στην έκφραση, μαζί με τους τύπους και τις τιμές τους. Για αυτήν την περίπτωση, περιμένουμε:

0 => Literal (2)1 => Variable (y)2 => Operator (+)3 => Literal (1)

Αρχικά, θα ορίσουμε μια τάξη Token για να κάνουμε τα πράγματα πιο εύκολα

function Token(type, value) { this.type = type; this.value = value}

Αλγόριθμος

Στη συνέχεια, ας φτιάξουμε τον σκελετό της λειτουργίας tokenizer.

Το tokenizer μας θα εξετάσει κάθε χαρακτήρα του strπίνακα και θα δημιουργήσει διακριτικά με βάση την τιμή που βρίσκει.

[Σημειώστε ότι υποθέτουμε ότι ο χρήστης μας δίνει μια έγκυρη έκφραση, επομένως θα παραλείψουμε οποιαδήποτε μορφή επικύρωσης σε αυτό το έργο.]

function tokenize(str) { var result=[]; //array of tokens // remove spaces; remember they don't matter? str.replace(/\s+/g, "");
 // convert to array of characters str=str.split("");
str.forEach(function (char, idx) { if(isDigit(char)) { result.push(new Token("Literal", char)); } else if (isLetter(char)) { result.push(new Token("Variable", char)); } else if (isOperator(char)) { result.push(new Token("Operator", char)); } else if (isLeftParenthesis(char)) { result.push(new Token("Left Parenthesis", char)); } else if (isRightParenthesis(char)) { result.push(new Token("Right Parenthesis", char)); } else if (isComma(char)) { result.push(new Token("Function Argument Separator", char)); } });
 return result;}

Ο παραπάνω κώδικας είναι αρκετά βασικός. Για την αναφορά, οι βοηθοί isDigit(), isLetter(), isOperator(), isLeftParenthesis(), και isRightParenthesis()ορίζονται ως εξής (δεν πρέπει να φοβάται από τα σύμβολα - αυτό λέγεται regex, και είναι πραγματικά φοβερό):

function isComma(ch) { return (ch === ",");}
function isDigit(ch) { return /\d/.test(ch);}
function isLetter(ch) { return /[a-z]/i.test(ch);}
function isOperator(ch) -
function isLeftParenthesis(ch) { return (ch === "(");}
function isRightParenthesis(ch) { return (ch == ")");}

[Σημειώστε ότι δεν υπάρχουν συναρτήσεις isFunction () , isLiteral () ή isVariable () , επειδή δοκιμάζουμε χαρακτήρες ξεχωριστά.]

Λοιπόν, τώρα ο αναλυτής μας λειτουργεί. Δοκιμάστε το με αυτές τις εκφράσεις: 2 + 3, 4a + 1, 5x + (2y), 11 + sin (20.4).

Ολα καλά?

ΟΧΙ ακριβως.

Θα παρατηρήσετε ότι για την τελευταία έκφραση, το 11 αναφέρεται ως δύο λογικά σύμβολα αντί για ένα. Αναφέρεται επίσης sinως τρία διακριτικά αντί για ένα. Γιατί είναι αυτό?

Let’s pause for a moment and think about this. We tokenized the array character by character, but actually, some of our tokens can contain multiple characters. For example, Literals can be 5, 7.9, .5. Functions can be sin, cos etc. Variables are only single-characters, but can occur together in implicit multiplication. How do we solve this?

Buffers

We can fix this by implementing a buffer. Two, actually. We’ll use one buffer to hold Literal characters (numbers and decimal point), and one for letters (which covers both variables and functions).

How do the buffers work? When the tokenizer encounters a number/decimal point or letter, it pushes it into the appropriate buffer, and keeps doing so until it enters a different kind of operator. Its actions will vary based on the operator.

For instance, in the expression 456.7xy + 6sin(7.04x) — min(a, 7), it should go along these lines:

read 4 => numberBuffer read 5 => numberBuffer read 6 => numberBuffer read . => numberBuffer read 7 => numberBuffer x is a letter, so put all the contents of numberbuffer together as a Literal 456.7 => result read x => letterBuffer read y => letterBuffer + is an Operator, so remove all the contents of letterbuffer separately as Variables x => result, y => result + => result read 6 => numberBuffer s is a letter, so put all the contents of numberbuffer together as a Literal 6 => result read s => letterBuffer read i => letterBuffer read n => letterBuffer ( is a Left Parenthesis, so put all the contents of letterbuffer together as a function sin => result read 7 => numberBuffer read . => numberBuffer read 0 => numberBuffer read 4 => numberBuffer x is a letter, so put all the contents of numberbuffer together as a Literal 7.04 => result read x => letterBuffer ) is a Right Parenthesis, so remove all the contents of letterbuffer separately as Variables x => result - is an Operator, but both buffers are empty, so there's nothing to remove read m => letterBuffer read i => letterBuffer read n => letterBuffer ( is a Left Parenthesis, so put all the contents of letterbuffer together as a function min => result read a=> letterBuffer , is a comma, so put all the contents of letterbuffer together as a Variable a => result, then push , as a Function Arg Separator => result read 7=> numberBuffer ) is a Right Parenthesis, so put all the contents of numberbuffer together as a Literal 7 => result

Complete. You get the hang of it now, right?

We’re getting there, just a few more cases to handle.

This is the point where you sit down and think deeply about your algorithm and data modeling. What happens if my current character is an operator, and the numberBuffer is non-empty? Can both buffers ever simultaneously be non-empty?

Putting it all together, here’s what we come up with (the values to the left of the arrow depict our current character (ch) type, NB=numberbuffer, LB=letterbuffer, LP=left parenthesis, RP=right parenthesis

loop through the array: what type is ch?
digit => push ch to NB decimal point => push ch to NB letter => join NB contents as one Literal and push to result, then push ch to LB operator => join NB contents as one Literal and push to result OR push LB contents separately as Variables, then push ch to result LP => join LB contents as one Function and push to result OR (join NB contents as one Literal and push to result, push Operator * to result), then push ch to result RP => join NB contents as one Literal and push to result, push LB contents separately as Variables, then push ch to result comma => join NB contents as one Literal and push to result, push LB contents separately as Variables, then push ch to result
end loop
join NB contents as one Literal and push to result, push LB contents separately as Variables,

Two things to note.

  1. Notice where I added “push Operator * to result”? That’s us converting the implicit multiplication to explicit. Also, when emptying the contents of LB separately as Variables, we need to remember to insert the multiplication Operator in between them.
  2. At the end of the function’s loop, we need to remember to empty whatever we have left in the buffers.

Translating It to Code

Putting it all together, your tokenize function should look like this now:

We can run a little demo:

var tokens = tokenize("89sin(45) + 2.2x/7");tokens.forEach(function(token, index) { console.log(index + "=> " + token.type + "(" + token.value + ")":});

Wrapping It Up

This is the point where you analyze your function and measure what it does versus what you want it to do. Ask yourself questions like, “Does the function work as intended?” and “Have I covered all edge cases?”

Οι ακραίες περιπτώσεις για αυτό θα μπορούσαν να περιλαμβάνουν αρνητικούς αριθμούς και παρόμοια. Εκτελείτε επίσης δοκιμές στη λειτουργία. Εάν στο τέλος είστε ικανοποιημένοι, τότε μπορείτε να αρχίσετε να αναζητάτε πώς μπορείτε να το βελτιώσετε.

Ευχαριστώ για την ανάγνωση. Κάντε κλικ στη μικρή καρδιά για να προτείνετε αυτό το άρθρο και μοιραστείτε αν σας άρεσε! Και αν έχετε δοκιμάσει μια άλλη προσέγγιση για τη δημιουργία ενός μαθηματικού tokenizer, ενημερώστε με στα σχόλια.