Giả sử chúng ta có ký pháp Ba Lan ngược (Reverse Polish Notation) và phải tính giá trị. Ký pháp Ba Lan ngược còn gọi là biểu thức hậu tố (postfix). Ta dùng cấu trúc dữ liệu stack để giải.
Từ biểu thức hậu tố, khi gặp toán hạng, đẩy vào stack. Khi gặp toán tử, lấy 2 phần tử từ stack, thực hiện phép toán theo đúng thứ tự. Kết quả đẩy lại vào stack. Sau khi duyệt xong, kết quả cuối cùng ở đỉnh stack. Ví dụ: "53+62/*35*+" cho kết quả 39.
Các bước:
- với mỗi ký tự ch trong biểu thức hậu tố
- nếu ch là toán tử ☉
- a := pop phần tử đầu từ stack
- b := pop phần tử thứ hai từ stack
- res := b ☉ a
- push res vào stack
- ngược lại nếu ch là toán hạng
- thêm ch vào stack
- nếu ch là toán tử ☉
- trả về phần tử đỉnh stack
Ví dụ (C++)
Hãy xem triển khai sau:
#include<iostream> #include<cmath> #include<stack> #include<climits> 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 << "Kết quả là: "<<postfixEval(post); }Input
"53+62/*35*+"
Output
Kết quả là: 39