Bài toán biểu thức Trung tố (Infix) - P1
1.Kí pháp trung tố
Là một cách biểu diễn phép toán hai ngôi. Khi biểu diễn phép toán, các kí hiệu toán tử nằm giữa các toán hạng. Ví dụ như a + b, a * b,... Khi biểu thức có nhiều phép toán, ta sử dụng cắp dấu ngoặc "(" và ")" để phân biết thứ tự ưu tiên giữa các phép toán. Nguyên tắc là *, /, %, ^ có thứ tự ưu tiên hơn + và -.
2. Thuật toán
Cho biểu thức đầu vào S là một chuỗi đã loại bỏ khoảng trắng, để đơn giản ta giả sử các toán tử chỉ có * / + - và các toán hạng chỉ có một chữ số.Khởi tạo hai Stack, một stack Operator để chứa các toán tử và Operand để chứa các toán hạng.
- Duyệt qua các phần tử của S từ 0 đến S.length
- Nếu S[i] là "(" thì đưa vào Operator
- Nếu S[i] là ")", lấy hai phần tử trên Operand thực hiện phép tính với phần tử trên Operator, kết quả thu được đẩy vào Operand đến khi phần tử trên đỉnh Operator là "(" thì loại bỏ nó ra khỏi Operator.
- Nếu toán tử S[i] có độ ưu tiên thấp hơn toán tử trên đỉnh Operator, lấy hai phần tử trên Operand thực hiện phép tính với toán tử trên đỉnh Operator. Kết quả đẩy vào Operand, S[i] đẩy vào Operator.
- Nếu toán tử S[i] có độ ưu tiên cao hơn toán tử trên đỉnh Operator thì đẩy S[i] vào Operator.
- Nếu S[i] là toán hạng đẩy vào Operand.
- Nếu duyệt qua hết độ dài S tiếp tục lấy hai phần tử trên Operand thực hiện phép tính với toán tử trên Operand đến khi Stack Operator rỗng thì dừng. Phần tử còn lại trong Operand chính là kết quả cuối cùng.
3.Minh họa giải thuật
VD: Có biểu thức S = "8 + (5 - 1) / 2";
-------------------Lặp với chiều dài của S---------------------
- S[0] = "8" -> Toán hạng, đẩy vào Operand.
Operand = [ 8 ] Operator = [ ]
- S[1] = "+" -> Toán tử, đẩy vào Operator.
Operand = [ 8 ] Operator = [ + ]
- S[2] = "(" - > Đẩy vào Operator.
Operand = [ 8 ] Operator = [ + , ( ]
- S[3] = "5" - > Toán hạng, Đẩy vào Operand.
Operand = [ 8 , 5 ] Operator = [ + , ( ]
- S[4] = "-" - > Toán tử đỉnh của Operator là "(" -> Đẩy vào Operator.
Operand = [ 8 , 5 ] Operator = [+ , ( , - ]
- S[5] = "1" - > Toán hạng, Đẩy vào Operand.
Operand = [ 8 , 5 , 1 ] Operator = [ + , ( , - ]
- S[6] = ")" - > Toán tử đỉnh của Operator: "-" != "(" -> 5 - 1 = 4 - > Đẩy 4 vào Operand
Operand = [ 8 , 4 ] Operator = [ + , ( ]
-> Đỉnh Operator == "(" -> Đẩy "(" ra khỏi Operator.
Operand = [ 8 , 4 ] Operator = [ + ]
- S[7] = "/" -> Toán tử có thứ tự cao hơn "+", Đẩy vào Operator.
Operand = [ 8 , 4 ] Operator = [ + , / ]
S[8] = "2" -> Toán hạng, Đẩy vào Operand.
Operand = [ 8 , 4 , 2 ] Operator = [ + , / ]
----------------------Kết thúc vòng lặp-------------------------
----------------------Vòng lặp với số phần tử trên stack Operator-------------------
Operand = [ 8 , 4 , 2 ] Operator = [ + , / ]
- Xét toán tử " / " -> Đẩy 4 / 2 = 2 vào Operand.
Operand = [ 8 , 2 ] Operator = [ + ]
- Xét toán tử " + " -> Đẩy 8 + 2 = 10 vào Operand.
Operand = [ 10 ] Operator = [ ]
=> END. Ta thu được kết quả bằng 10.
4.Mã giả
void infixCal(S)
{
for(i = 0; i < S.length; i++)
{
if(S[i] == "(") //S[i] là dấu "("
Operator.push(S[i]);
else if(S[i] == ")") //S[i] là dấu ")"
{
while(Operator.peek() != "(") //Vọng lặp đến khi đỉnh của Operator là dấu "("
{
b = Operand.pop();
a = Operand.pop();
x = Operator.pop();
Operand.push(calculator(a, b, x)); //Đẩy kết quả của biểu thức a và b với toán tử x vào stack Operand.
}
Operator.pop(); //Lấy "(" ra khỏi stack Operator
}
else if(isOperator(S[i])) // Hàm isOperator kiểm tra S[i] có phải toán tử không.
{
if(infix(S[i]) < infix(Operator.peek()) // Nếu thứ tự ưu tiên S[i] nhỏ hơn hoặc bằng toán tử đỉnh Operator(Hàm infix xác định độ ưu tiên)
{
b = Operand.pop();
a = Operand.pop();
x = Operator.pop();
Operand.push(calculator(a, b, x)); //Đẩy kết quả của biểu thức a và b với toán tử x vào stack Operand.
}
else //Nếu thứ tự ưu tiền S[i] lớn hơn đỉnh Operator
Operator.push(S[i]);
}
else // Nếu S[i] là toán hạng
Operand.push(S[i]);
}
//Duyệt hết các phanf tử trong stack Operator
while(!Operator.isEmpty())
{
b = Operand.pop();
a = Operand.pop();
x = Operator.pop();
Operand.push(calculator(a, b, x)); //Đẩy kết quả của biểu thức a và b với toán tử x vào stack Operand.
}
printf("Phan tu cuoi trong Operand la ket qua cua bieu thuc: ", Operator.push());
}
{
for(i = 0; i < S.length; i++)
{
if(S[i] == "(") //S[i] là dấu "("
Operator.push(S[i]);
else if(S[i] == ")") //S[i] là dấu ")"
{
while(Operator.peek() != "(") //Vọng lặp đến khi đỉnh của Operator là dấu "("
{
b = Operand.pop();
a = Operand.pop();
x = Operator.pop();
Operand.push(calculator(a, b, x)); //Đẩy kết quả của biểu thức a và b với toán tử x vào stack Operand.
}
Operator.pop(); //Lấy "(" ra khỏi stack Operator
}
else if(isOperator(S[i])) // Hàm isOperator kiểm tra S[i] có phải toán tử không.
{
if(infix(S[i]) < infix(Operator.peek()) // Nếu thứ tự ưu tiên S[i] nhỏ hơn hoặc bằng toán tử đỉnh Operator(Hàm infix xác định độ ưu tiên)
{
b = Operand.pop();
a = Operand.pop();
x = Operator.pop();
Operand.push(calculator(a, b, x)); //Đẩy kết quả của biểu thức a và b với toán tử x vào stack Operand.
}
else //Nếu thứ tự ưu tiền S[i] lớn hơn đỉnh Operator
Operator.push(S[i]);
}
else // Nếu S[i] là toán hạng
Operand.push(S[i]);
}
//Duyệt hết các phanf tử trong stack Operator
while(!Operator.isEmpty())
{
b = Operand.pop();
a = Operand.pop();
x = Operator.pop();
Operand.push(calculator(a, b, x)); //Đẩy kết quả của biểu thức a và b với toán tử x vào stack Operand.
}
printf("Phan tu cuoi trong Operand la ket qua cua bieu thuc: ", Operator.push());
}
Nhận xét
Đăng nhận xét