Trong bài viết này, chúng ta sẽ thảo luận về việc đánh giá biểu thức tiền tố.
Biểu thức tiền tố
Trong ký hiệu này, toán tử là tiền tố cho toán hạng, tức là toán tử được viết trước toán hạng. Ví dụ: + ab . Điều này tương đương với ký hiệu tiền tố a + b . Ký hiệu tiền tố còn được gọi là Ký hiệu Ba Lan .
Để đọc thêm.
Ví dụ:
* + 6 9 - 3 1
Biểu thức tiền tố được đánh giá nhanh hơn biểu thức tiền tố. Ngoài ra, không có dấu ngoặc trong biểu thức tiền tố làm cho nó đánh giá nhanh hơn.
Thuật toán để đánh giá Biểu thức tiền tố:
Việc đánh giá biểu thức tiền tố yêu cầu cấu trúc dữ liệu ngăn xếp. Chúng tôi sẽ đẩy các toán tử trong ngăn xếp và sau đó giải biểu thức.
Chúng ta sẽ lần lượt đi thăm từng phần tử của biểu thức. Nếu phần tử hiện tại là một toán hạng, chúng tôi sẽ đẩy nó vào ngăn xếp. Và nếu đó là một toán tử, chúng ta sẽ bật hai toán hạng, thực hiện thao tác, toán hạng toán tử và sau đó đẩy kết quả trở lại ngăn xếp.
Thuật toán -
Bước 1: Bắt đầu từ phần tử cuối cùng của biểu thức.
Bước 2: kiểm tra phần tử hiện tại.
Bước 2.1: nếu nó là một toán hạng, hãy đẩy nó vào ngăn xếp.
Bước 2.2: Nếu đó là một toán tử, hãy bật hai toán hạng từ ngăn xếp. Thực hiện thao tác và đẩy các phần tử trở lại ngăn xếp.
Bước 3: Làm điều này cho đến khi tất cả các phần tử của biểu thức được duyệt và trả về phần trên cùng của ngăn xếp, đây sẽ là kết quả của phép toán.
Cho phép xem hoạt động của thuật toán của chúng tôi để giải quyết một biểu thức tiền tố,
Biểu thức tiền tố:
* + 6 9 - 3 1
Lặp lại:1
Phần tử được quét => 1
Hoạt động => đẩy vào ngăn xếp
Ngăn xếp => 1
Lặp lại:2
Phần tử được quét => 3
Hoạt động => đẩy vào ngăn xếp
Ngăn xếp => 3, 1
Lặp lại:3
Đã quét phần tử => -
Hoạt động => bật hai từ ngăn xếp, thực hiện hoạt động và đẩy lại kết quả.
3 - 1 =2
Ngăn xếp => 2
Lặp lại:4
Phần tử được quét => 9
Hoạt động => đẩy vào ngăn xếp
Ngăn xếp => 9, 2
Lặp lại:5
Đã quét phần tử => 6
Hoạt động => đẩy vào ngăn xếp
Ngăn xếp => 6, 9, 2
Lặp lại:6
Đã quét phần tử => +
Hoạt động => bật hai từ ngăn xếp, thực hiện hoạt động và đẩy lại kết quả.
6 + 9 =15
Ngăn xếp => 15, 2
Lặp lại:7
Đã quét phần tử => *
Hoạt động => bật hai từ ngăn xếp, thực hiện hoạt động và đẩy lại kết quả.
15 * 2 =30
Ngăn xếp => 30
Kết thúc => trả về đầu ngăn xếp, kết quả =30.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <bits/stdc++.h>
using namespace std;
double evaluatePrefix(string prefixExp) {
stack<double> operendStack;
int size = prefixExp.size() - 1;
for (int i = size; i >= 0; i--) {
if (isdigit(prefixExp[i]))
operendStack.push(prefixExp[i] - '0');
else {
double o1 = operendStack.top();
operendStack.pop();
double o2 = operendStack.top();
operendStack.pop();
if( prefixExp[i] == '+')
operendStack.push(o1 + o2);
else if( prefixExp[i] == '-')
operendStack.push(o1 - o2);
else if( prefixExp[i] == '*')
operendStack.push(o1 * o2);
else if( prefixExp[i] == '/')
operendStack.push(o1 / o2);
else{
cout<<"Invalid Expression";
return -1;
}
}
}
return operendStack.top();
}
int main()
{
string prefixExp = "*+69-31";
cout<<"The result of evaluation of expression "<<prefixExp<<" is "<<evaluatePrefix(prefixExp);
return 0;
} Đầu ra -
The result of evaluation of expression *+69-31 is 30