HomeLập trìnhJavaScriptCách tạo mã...

Cách tạo mã thông báo biểu thức toán học bằng JavaScript (hoặc bất kỳ ngôn ngữ nào khác)


bởi Shalvah

1*cgIB8FPxdoWvQtgm9JazIA
Nguồn: Wikimedia Commons

Cách đây một thời gian, tôi có cảm hứng xây dựng một ứng dụng để giải các loại bài toán cụ thể. Tôi phát hiện ra rằng mình phải phân tích biểu thức thành một cây cú pháp trừu tượng, vì vậy tôi quyết định xây dựng một nguyên mẫu trong Javascript. Trong khi làm việc trên trình phân tích cú pháp, tôi nhận ra rằng trước tiên phải xây dựng bộ mã thông báo. Tôi sẽ hướng dẫn bạn cách tự làm. (Cảnh báo: nó dễ hơn so với lúc đầu.)

Tokenizer là gì?

Trình mã thông báo là một chương trình chia biểu thức thành các đơn vị được gọi là mã thông báo. Chẳng hạn, nếu chúng tôi có một biểu thức như “Tôi là một nhà phát triển to béo”, chúng tôi có thể mã hóa nó theo nhiều cách khác nhau, chẳng hạn như:

Sử dụng các từ như mã thông báo,

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

Sử dụng các ký tự không phải khoảng trắng làm mã thông báo,

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

Chúng tôi cũng có thể coi tất cả các ký tự là mã thông báo, để có được

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

Bạn có được ý tưởng, phải không?

Tokenizers (còn được gọi là từ vựng) được sử dụng để phát triển trình biên dịch cho ngôn ngữ lập trình. Chúng giúp trình biên dịch hiểu được cấu trúc của những gì bạn đang cố nói. Tuy nhiên, trong trường hợp này, chúng tôi đang xây dựng một biểu thức toán học.

mã thông báo

Một biểu thức toán học hợp lệ bao gồm các mã thông báo hợp lệ về mặt toán học, vì mục đích của dự án này có thể là chữ, Biến, Toán tử, hàm hoặc Dấu tách đối số chức năng.
Một vài lưu ý ở trên:

  • Nghĩa đen là một tên ưa thích cho một số (trong trường hợp này). Chúng tôi sẽ chỉ cho phép các số ở dạng nguyên hoặc thập phân.
  • Biến là loại bạn đã quen dùng trong toán học: a,b,c,x,y,z. Đối với dự án này, tất cả các biến được giới hạn ở tên một chữ cái (vì vậy không có gì giống như biến1 hoặc giá bán). Điều này là để chúng tôi có thể mã hóa một biểu thức như mẹ là sản phẩm của các biến tôimộtvà không phải là một biến duy nhất mẹ.
  • Toán tử hành động trên Chữ và Biến và kết quả của các hàm. Chúng tôi sẽ cho phép các toán tử +, -, *, / và ^.
  • Chức năng là hoạt động “nâng cao hơn”. Chúng bao gồm những thứ như sin(), cos(), tan(), min(), max(), v.v.
  • Dấu tách đối số chức năng chỉ là một tên ưa thích cho dấu phẩy, được sử dụng trong ngữ cảnh như sau: tối đa (4, 5) (giá trị lớn nhất trong hai giá trị). Chúng tôi gọi nó là Dấu phân cách đối số hàm bởi vì nó phân tách các đối số hàm (đối với các hàm nhận hai hoặc nhiều đối số, chẳng hạn như tối đa tối thiểu).

Chúng tôi cũng sẽ thêm hai mã thông báo thường không được coi là mã thông báo, nhưng sẽ giúp chúng tôi hiểu rõ: Trái Dấu ngoặc phải. Bạn biết đó là gì.

Đọc thêm  JavaScript setTimeout() – JS Timer để trì hoãn N giây

Một vài cân nhắc

phép nhân ẩn

Phép nhân ẩn đơn giản có nghĩa là cho phép người dùng viết các phép nhân “tốc ký”, chẳng hạn như 5xthay vì 5*x. Tiến thêm một bước nữa, nó cũng cho phép thực hiện điều đó với các chức năng (5sin(x) = 5*tội lỗi(x)).

Hơn nữa, nó cho phép 5(x) và 5(sin(x)). Chúng tôi có tùy chọn cho phép hoặc không. Đánh đổi? Việc không cho phép nó thực sự sẽ làm cho việc mã hóa dễ dàng hơn và sẽ cho phép các tên biến có nhiều chữ cái (các tên nhưprice). Việc cho phép nó làm cho nền tảng trở nên trực quan hơn đối với người dùng, đồng thời cung cấp thêm một thách thức cần vượt qua. Tôi đã chọn để cho phép nó.

cú pháp

Mặc dù chúng tôi không tạo ngôn ngữ lập trình, nhưng chúng tôi cần có một số quy tắc về những gì tạo nên một biểu thức hợp lệ, để người dùng biết những gì cần nhập và chúng tôi biết những gì cần lập kế hoạch. Nói một cách chính xác, các mã thông báo toán học phải được kết hợp theo các quy tắc cú pháp này để biểu thức hợp lệ. Đây là quy tắc của tôi:

  1. Các mã thông báo có thể được phân tách bằng 0 hoặc nhiều ký tự khoảng trắng
2+3, 2 +3, 2 + 3, 2 + 3 are all OK 5 x - 22, 5x-22, 5x- 22 are all OK

Nói cách khác, khoảng cách không quan trọng (ngoại trừ trong mã thông báo nhiều ký tự như Literal 22).

2. Các đối số của hàm phải nằm trong dấu ngoặc đơn (tội lỗi(y), cos(45)không phải tội lỗi, cos 45). (Tại sao? Chúng ta sẽ xóa tất cả các khoảng trắng khỏi chuỗi, vì vậy chúng ta muốn biết vị trí bắt đầu và kết thúc của một hàm mà không cần phải thực hiện một số “bài tập thể dục”.)

3. Phép nhân ẩn chỉ được phép giữa Chữ và biếnhoặc Nghĩa đen và chức năng, theo thứ tự đó (nghĩa là Chữ luôn xuất hiện trước) và có thể có hoặc không có dấu ngoặc đơn. Điều này có nghĩa là:

  • một(4) sẽ được coi là một lệnh gọi hàm chứ không phải một*4
  • a4 không được phép
  • 4a4(a) vẫn ổn

Bây giờ, chúng ta hãy bắt tay vào việc.

Mô hình hóa dữ liệu

Sẽ rất hữu ích nếu bạn có một biểu thức mẫu trong đầu để kiểm tra điều này. Chúng ta sẽ bắt đầu với một cái gì đó cơ bản: 2y + 1

Những gì chúng tôi mong đợi là một mảng liệt kê các mã thông báo khác nhau trong biểu thức, cùng với các loại và giá trị của chúng. Vì vậy, đối với trường hợp này, chúng tôi mong đợi:

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

Đầu tiên, chúng ta sẽ định nghĩa một lớp Token để giúp mọi việc dễ dàng hơn:

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

thuật toán

Tiếp theo, hãy xây dựng bộ khung của chức năng mã thông báo của chúng tôi.

Trình mã thông báo của chúng tôi sẽ đi qua từng ký tự của str mảng và tạo mã thông báo dựa trên giá trị mà nó tìm thấy.

[Note that we’re assuming the user gives us a valid expression, so we’ll skip any form of validation throughout this project.]

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

Đoạn mã trên khá cơ bản. Để tham khảo, những người trợ giúp isDigit() , isLetter(), isOperator(), isLeftParenthesis()isRightParenthesis()được định nghĩa như sau (đừng sợ các ký hiệu — nó được gọi là biểu thức chính quy và nó thực sự tuyệt vời):

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

[Note that there are no isFunction(), isLiteral() or isVariable() functions, because we testing characters individually.]

Vì vậy, bây giờ trình phân tích cú pháp của chúng tôi thực sự hoạt động. Hãy thử với các biểu thức sau: 2 + 3, 4a + 1, 5x+ (2y), 11 + sin(20,4).

Đọc thêm  Cách kiểm tra xem đầu vào có trống không bằng JavaScript

Tất cả đều tốt?

Không hẳn.

Bạn sẽ quan sát thấy rằng đối với biểu thức cuối cùng, 11 được báo cáo là hai Mã thông báo theo nghĩa đen thay vì một. Cũng thế sin được báo cáo là số ba mã thông báo thay vì một. Tại sao lại thế này?

Hãy tạm dừng một chút và suy nghĩ về điều này. Chúng tôi đã mã hóa từng ký tự của mảng, nhưng trên thực tế, một số mã thông báo của chúng tôi có thể chứa nhiều ký tự. Ví dụ: Chữ có thể là 5, 7.9, .5. Các hàm có thể là sin, cos, v.v. Các biến chỉ là các ký tự đơn, nhưng có thể xuất hiện cùng nhau trong phép nhân ngầm định. Làm thế nào để chúng tôi giải quyết điều này?

bộ đệm

Chúng ta có thể khắc phục điều này bằng cách triển khai bộ đệm. Hai, thực sự. Chúng tôi sẽ sử dụng một bộ đệm để giữ các ký tự Chữ (số và dấu thập phân) và một bộ đệm cho các chữ cái (bao gồm cả biến và hàm).

Làm thế nào để các bộ đệm làm việc? Khi bộ mã thông báo gặp một số/dấu thập phân hoặc chữ cái, nó sẽ đẩy nó vào bộ đệm thích hợp và tiếp tục làm như vậy cho đến khi nhập vào một loại toán tử khác. Hành động của nó sẽ thay đổi dựa trên người điều hành.

Chẳng hạn, trong biểu thức 456,7xy + 6sin(7,04x) — tối thiểu(a, 7)nó sẽ đi theo những dòng sau:

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

Hoàn chỉnh. Bây giờ bạn hiểu rõ về nó, phải không?

Đọc thêm  Cách cắt và ghép các mảng trong JavaScript

Chúng tôi đang đến đó, chỉ còn một vài trường hợp nữa để xử lý.

Đây là thời điểm mà bạn ngồi xuống và suy nghĩ sâu sắc về thuật toán và mô hình hóa dữ liệu của mình. Điều gì xảy ra nếu ký tự hiện tại của tôi là một toán tử và sốBuffer không trống? Cả hai bộ đệm có thể đồng thời không trống không?

Đặt tất cả lại với nhau, đây là những gì chúng tôi nghĩ ra (các giá trị ở bên trái của mũi tên mô tả loại ký tự (ch) hiện tại của chúng tôi, NB=bộ đệm số, LB=bộ đệm chữ, LP=dấu ngoặc đơn bên trái, RP=dấu ngoặc đơn bên phải

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,

Hai điều cần lưu ý.

  1. Lưu ý nơi tôi đã thêm “push Operator * to result”? Đó là chúng ta chuyển phép nhân ẩn sang tường minh. Ngoài ra, khi xóa riêng nội dung của LB dưới dạng Biến, chúng ta cần nhớ chèn Toán tử nhân vào giữa chúng.
  2. Ở cuối vòng lặp của hàm, chúng ta cần nhớ làm trống bất cứ thứ gì chúng ta còn lại trong bộ đệm.

Dịch nó sang mã

Đặt tất cả lại với nhau, chức năng tokenize của bạn bây giờ sẽ trông như thế này:

Chúng ta có thể chạy một bản demo nhỏ:

var tokens = tokenize("89sin(45) + 2.2x/7");tokens.forEach(function(token, index) {  console.log(index + "=> " + token.type + "(" + token.value + ")":});
1*dRLwtjvcAXiO8OekLuxpgg
Ừ! Lưu ý * s được thêm vào cho các phép nhân ngầm định

gói nó lên

Đây là điểm mà bạn phân tích chức năng của mình và đo lường những gì nó làm so với những gì bạn muốn nó làm. Hãy tự hỏi mình những câu hỏi như, “Chức năng này có hoạt động như dự định không?” và “Tôi đã bao gồm tất cả các trường hợp cạnh chưa?”

Các trường hợp cạnh cho điều này có thể bao gồm các số âm và những thứ tương tự. Bạn cũng chạy thử nghiệm trên chức năng. Nếu cuối cùng bạn hài lòng, thì bạn có thể bắt đầu tìm cách cải thiện nó.

Cảm ơn vì đã đọc. Vui lòng nhấp vào trái tim nhỏ để giới thiệu bài viết này và chia sẻ nếu bạn thích nó! Và nếu bạn đã thử một cách tiếp cận khác để xây dựng mã thông báo toán học, hãy cho tôi biết trong phần nhận xét.



Zik.vn – Biên dịch & Biên soạn Lại

spot_img

Create a website from scratch

Just drag and drop elements in a page to get started with Newspaper Theme.

Buy Now ⟶

Bài viết liên quang

DMCA.com Protection Status