Matematikai kifejezés tokenizer készítése JavaScript (vagy bármely más nyelv) használatával

Valamikor ezelőtt inspirálódtam egy alkalmazás készítéséhez matematikai problémák speciális fajtáinak megoldására. Rájöttem, hogy a kifejezést absztrakt szintaxisfává kell elemeznem, ezért úgy döntöttem, hogy prototípust építek a Javascriptben. Az elemzőn dolgozva rájöttem, hogy először a tokenizátort kell megépíteni. Végigvezetlek benneteket, hogyan csináljatok egyet. (Figyelem: könnyebb, mint amilyennek elsőre tűnik.)

Mi az a Tokenizer?

A felismerő olyan program, amely bomlik fel egy kifejezés nevezett egységekre jelzőt . Például, ha van olyan kifejezésünk, mint „nagy kövér fejlesztő vagyok”, akkor ezt különböző módon tudnánk kódolni, például:

A szavak használata tokenekként,

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

Nem szóköz karakterek használata tokenekként,

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

Az összes karaktert tokennek is tekinthetjük, hogy megszerezzük

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

Érted az ötletet, igaz?

A tokenizátorokat (más néven lexerek) a fordítóprogramok fejlesztésére használják a programozási nyelvekhez. Segítenek a fordítónak strukturális értelmet adni abból, amit mondani próbál. Ebben az esetben azonban matematikai kifejezésekre építünk egyet.

Tokenek

Az érvényes matematikai kifejezés matematikailag érvényes tokenekből áll, amelyek a projekt szempontjából lehetnek Literals , Variables , Operators, Functions vagy Function Argument Separators .

Néhány megjegyzés a fentiekről:

  • A Literal egy szám fantázianév (ebben az esetben). Csak egész vagy tizedes formában engedélyezzük a számokat.
  • A változó az a fajta, amelyet a matematikában szokott: a, b, c, x, y, z. Ennél a projektnél az összes változó egybetűs nevekre korlátozódik (tehát semmi olyan, mint a var1 vagy az ár ). Ez így is tokenize kifejezése, mint ma , mint a termék a változók m és egy , nem egyetlen változó ma .
  • Az operátorok a literálokra és a változókra, valamint a funkciók eredményeire hatnak. Engedélyezzük a +, -, *, / és a ^ operátoroknak.
  • A funkciók „fejlettebb” műveletek. Ilyenek például a bűn (), a cos (), a tan (), a min (), a max () stb
  • A Function Argument Separator csak egy vessző fantázianév, amelyet ilyen kontextusban használnak: max (4, 5) (a két érték közül az egyik maximum). Funkció-argumentum elválasztónak hívjuk, mert jól elválasztja a függvény-argumentumokat (olyan függvényekhez, amelyek két vagy több argumentumot vesznek fel, például max és min ).

Két olyan tokent is felveszünk, amelyek általában nem tekinthetők tokeneknek, de egyértelműséggel segítenek bennünket: Bal és Jobb zárójelek . Tudod, mik ezek.

Néhány szempont

Implicit szorzás

Az implicit szorzás egyszerűen azt jelenti, hogy lehetővé teszi a felhasználó számára , hogy 5 * x helyett "gyors" szorzókat írjon, például 5x . Továbblépve lehetővé teszi ezt az ( 5sin (x) = 5 * sin (x) ) függvényekkel is .

Még ennél is többet tesz lehetővé 5 (x) és 5 (sin (x)). Lehetőségünk van engedélyezni vagy sem. Kompromisszumok? Ha nem engedi meg, az valójában megkönnyítené a tokenezést, és több betűs változóneveket (például neveket price) tenne lehetővé . Ha lehetővé teszi, a platform intuitívabbá válik a felhasználó számára, és további kihívást jelent a leküzdéshez. Úgy döntöttem, hogy megengedem.

Szintaxis

Noha nem készítünk programozási nyelvet, rendelkeznünk kell bizonyos szabályokkal arról, hogy mitől érvényes kifejezés, így a felhasználók tudják, mit kell beírni, és mi tudjuk, mit tervezzünk. Pontosabban, a matematikai tokeneknek ezeket a szintaxis-szabályokat kell kombinálniuk, hogy a kifejezés érvényes legyen. Itt vannak a szabályaim:

  1. A tokenek 0 vagy több szóközzel elválaszthatók
2+3, 2 +3, 2 + 3, 2 + 3 are all OK 5 x - 22, 5x-22, 5x- 22 are all OK

Más szóval, a szóköz nem számít (kivéve egy több karakterből álló tokenen belül, mint például a Literal 22).

2. A függvény argumentumoknak zárójelben kell lenniük ( sin (y) , cos (45) , nem sin y , cos 45 ). (Miért? Az összes szóközt eltávolítjuk a karaktersorozatból, ezért szeretnénk megtudni, hogy egy függvény hol kezdődik és ér véget, anélkül, hogy valamilyen „tornát” kellene végeznünk.)

3. Az implicit szaporítás csak az Literals és a Variables vagy a Literals and Functions között engedélyezett ebben a sorrendben (vagyis a Literals mindig az első), és lehet zárójelekkel vagy zárójelekkel. Ez azt jelenti, hogy:

  • az a (4) függvényhívásként fog kezelni, nem pedig a * 4- ként
  • a4 nem megengedett
  • A 4a. És a 4. a) pontok rendben vannak

Most kezdjünk dolgozni.

Adatok modellezése

Segít, ha egy minta kifejezés van a fejében, hogy ezt tesztelje. Kezdünk valami alapvetővel: 2 év + 1

Arra számítunk, hogy egy tömb, amely felsorolja a kifejezés különböző tokenjeit, típusaikkal és értékeikkel együtt. Tehát ebben az esetben a következőket várjuk:

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

Először meghatározunk egy Token osztályt, hogy megkönnyítsük a dolgokat:

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

Algoritmus

Ezután készítsük el a tokenizer függvény vázát.

Tokenizálónk végigmegy a strtömb minden karakterén, és a megtalált érték alapján készít tokeneket.

[Ne feledje, hogy feltételezzük, hogy a felhasználó érvényes kifejezést ad nekünk, ezért az érvényesítés bármilyen formáját kihagyjuk a projekt során.]

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;}

A fenti kód meglehetősen egyszerű. Referenciaként a segítők isDigit(), isLetter(), isOperator(), isLeftParenthesis(), és isRightParenthesis()a következőképpen határozzák meg (ne félj a szimbólumok - ezt hívják regex, és ez tényleg félelmetes):

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 == ")");}

[Vegye figyelembe, hogy nincsenek isFunction () , isLiteral () vagy isVariable () függvények, mert a karaktereket egyenként teszteljük.]

Tehát most értelmezőnk valóban működik. Próbálja ki a következő kifejezésekkel: 2 + 3, 4a + 1, 5x + (2y), 11 + bűn (20.4).

Minden rendben?

Nem egészen.

Megfigyeli, hogy az utolsó kifejezésnél a 11-et két literál tokenként jelentik egy helyett. Ugyancsak három zsetonként sinkap jelentést egy helyett. Miért ez?

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?”

Edge cases for this could include negative numbers and the like. You also run tests on the function. If at the end you are satisfied, you may then begin to seek out how you can improve it.

Thanks for reading. Please click the little heart to recommend this article, and share if you enjoyed it! And if you have tried another approach for building a math tokenizer, do let me know in the comments.