Mở đầuTôi đã học về cấu trúc dữ liệu stack khi còn học ở trường đại học, một trong những ví dụ kinh điển có sử dụng cấu trúc stack là thuật toán biểu thức Postfix. Khi bắt đầu học JS tôi có đọc 2 cuốn sách Eloquent Javascript và Javascript: The Good Parts. Tôi nhận ra rằng, có một cách để nâng cao trình độ JS của mình – Mô tả các cấu trúc dữ liệu cơ bản bằng JS, triển khai các thuật toán cơ bản bằng JS. Đó là lý do tôi viết bài viết này. Biểu thức PostfixBiểu thức toán học Postfix(hậu tố) là biểu thức có phép toán nằm sau toán tử. Công thức cơ bản nhất của biểu thức Postfix: Toán_tử_1 Toán_tử_2 Phép_toán. Điều này thì khác hoàn toàn với biểu thức Infix(trung tố), nơi chúng ta có các phép toán thì nằm giữa các toán tử.Toán_tử_1 Toán_tử_2 Phép_toán. Điều này thì khác hoàn toàn với biểu thức Infix(trung tố), nơi chúng ta có các phép toán thì nằm giữa các toán tử. Ta có một ví dụ, biểu thức Infix 3 + 7 thì tương đương với biểu thức Postfix 3 7 + . Một biểu thức Postfix có thể là một nhóm các toán hạng trong một biểu thức Postfix khác: 5 3 + 4 * thì tương đương (5 + 3 ) * 4 . Vì một biểu thức sẽ thực hiện ngay khi nó gặp một phép toán, nên chúng ta không cần các dấu ngoặc tròn (“(“) để chỉ thứ tự các biểu thức. Chúng ta có một biểu thức Infix (3 * 4 / (2 + 5)) * (3 + 7) nó sẽ tương đương với biểu thức Postfix 3 4 * 2 5 + / 3 7 + * . Nó có chút khó hiểu. Tôi sẽ đi qua từng phần của biểu thức để chúng ta có thể hiểu nó.
Với biểu thức Postfix, chúng ta dễ dàng để mô tả cho máy tính hiểu được các phép toán, đặc biệt là thứ tự ưu tiên của các phép toán. Thuật toánChuyển Infix to PostfixTrước tiên chúng ta sẽ tìm hiểu về cách chuyển đổi các biểu thức quen thuộc với chúng ta(Infix) sang dạng biểu thức máy tính có thể tính toán được (Postfix). Chúng ta sẽ sử dụng stack cho thuật toán này (các bạn có thể đọc thêm về stack để hiểu rõ hơn): Ta cho vòng lặp chạy hết chuỗi:
Hoàn tất vòng lặp, nếu vẫn còn phần tử trong Stack thì ta lần lượt Pop các phần tử đó trong mảng Stack và Push vào Output. Có vẻ hơi khó hiểu, chúng ta sẽ xem qua ví dụ: Chuyển đổi biểu thức 5.5/2 + 3*(4/8 – 2) sang Postfix  Hoặc các bạn có thể xem ở video này Thực hiện thuật toán bằng JS function infixToPostfix(input) {
let stack = [], answer = [], char;
const operands = {
'+': 1,
'-': 1,
"*": 2,
"/": 2,
};
for (let char of input.split(' ')) {
let currentPrecedence = operands[char];
if (currentPrecedence) {
let peek = operands[stack[stack.length - 1]];
// pop until the peek is smaller
while (peek >= currentPrecedence) {
answer.push(stack.pop());
peek = operands[stack[stack.length - 1]];
}
stack.push(char);
} else { // not operand, push to answer
answer.push(char);
}
}
while (stack.length > 0) {
answer.push(stack.pop())
}
return answer.join(' ');
}Tính toán biểu thức PostfixKhi chuyển đổi sang Postfix thì việc tính toán trở nên đơn giản hơn khi còn là Infix. Thuật toán phần này cũng sử dụng stack: Ta duyệt vòng lặp trong mảng Input:
Kết thúc vòng lặp, phần tử duy nhất trong Stack chính là kết quả cuối cùng Triển khai thuật toán bằng JS function executePostfix(str) {
let stack = [], operand1, operand2, tempOperand;
let operators = ['+', '-', '*', '/'];
for (let char of str.split(' ')) {
// char = str.charAt(i);
if (operators.indexOf(char) >= 0) {
// operate
operand2 = stack.pop();
operand1 = stack.pop();
tempOperand = eval(operand1 + char + operand2);
stack.push(tempOperand);
} else {
stack.push(char);
}
}
return stack.pop();
}Kiểu tra: Chúng ta sẽ tính toán biểu thức: let expression = infixToPostfix('20 + 3 * 3 + 7');
let answer = executePostfix(expression);
console.log(expression, '\n', answer);Kết quả: 20 3 3 * + 7 + 36 Kết luậnTrên đây là bài hướng dẫn về Thuật toán tính toán biểu thức Postfix, cảm ơn các bạn đã chú ý theo dõi. Hẹn gặp lại ở những bài viết sau! |
