Để giải biểu thức toán học, chúng ta cần dạng tiền tố hoặc hậu tố. Sau khi chuyển đổi infix thành postfix, chúng tôi cần thuật toán đánh giá postfix để tìm ra câu trả lời chính xác.
Ở đây chúng ta cũng phải sử dụng cấu trúc dữ liệu ngăn xếp để giải các biểu thức postfix.
Từ biểu thức hậu tố, khi một số toán hạng được tìm thấy, hãy đẩy chúng vào ngăn xếp. Khi một toán tử nào đó được tìm thấy, hai mục sẽ xuất hiện từ ngăn xếp và sau đó hoạt động được thực hiện theo đúng trình tự. Sau đó, kết quả cũng được đẩy vào ngăn xếp để sử dụng trong tương lai. Sau khi hoàn thành toàn bộ biểu thức, kết quả cuối cùng cũng được lưu trữ trong ngăn xếp.
Input: Postfix expression: 53+62/*35*+ Output: The result is: 39
Thuật toán
postfixEvaluation (hậu tố)
Đầu vào :Biểu thức hậu tố để đánh giá.
Đầu ra :Câu trả lời sau khi đánh giá biểu mẫu postfix.
Begin
for each character ch in the postfix expression, do
if ch is an operator , then
a := pop first element from stack
b := pop second element from the stack
res := b a
push res into the stack
else if ch is an operand, then
add ch into the stack
done
return element of stack top
End Mã mẫu
#include<iostream>
#include<cmath>
#include<stack>
using namespace std;
float scanNum(char ch) {
int value;
value = ch;
return float(value-'0'); //return float from character
}
int isOperator(char ch) {
if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
return 1; //character is an operator
return -1; //not an operator
}
int isOperand(char ch) {
if(ch >= '0' && ch <= '9')
return 1; //character is an operand
return -1; //not an operand
}
float operation(int a, int b, char op) {
//Perform operation
if(op == '+')
return b+a;
else if(op == '-')
return b-a;
else if(op == '*')
return b*a;
else if(op == '/')
return b/a;
else if(op == '^')
return pow(b,a); //find b^a
else
return INT_MIN; //return negative infinity
}
float postfixEval(string postfix) {
int a, b;
stack<float> stk;
string::iterator it;
for(it=postfix.begin(); it!=postfix.end(); it++) {
//read elements and perform postfix evaluation
if(isOperator(*it) != -1) {
a = stk.top();
stk.pop();
b = stk.top();
stk.pop();
stk.push(operation(a, b, *it));
}else if(isOperand(*it) > 0) {
stk.push(scanNum(*it));
}
}
return stk.top();
}
main() {
string post = "53+62/*35*+";
cout << "The result is: "<<postfixEval(post);
} Đầu ra
The result is: 39