Phương pháp chuyển đổi biểu thức inFix sang postFix như sau : (Trích sách Cấu trúc dữ liệu và thuật toán )
Nếu thành phần được đọc là toán hạng thì viết nó vào biểu thức postFix
Nếu thành phần được đọc là dấu mở ngoặc thì đẩy nó vào stack
Nếu thành phần được đọc là dấu đóng ngoặc thì lấy các phép toán trong stack ra và viết nó vào biểu thức postFix cho tới khi gặp dấu mở ngoặc.
Sau đó loại dấu mở ngoặc khỏi stack
Nếu thành phần là phép toán thì xét các trường hợp sau
Nếu stack không rỗng, hoặc phần tử ở đỉnh stack có độ ưu tiên cao hơn hay bằng phép toán hiện thời thì lấy phép toán đó ra khỏi stack và đưa vào postFix. Lặp lại bước này
Nếu stack rỗng, hoặc phần tử ở đỉnh stack có độ ưu tiên thấp hơn phép toán hiện thời thì phép toán hiện thời được đẩy vào stack
Sau khi toàn bộ biểu thức inFix đã được đọc thì lấy các phép toán trong ngăn xếp ra và viết vào postFix cho đến khi ngăn xếp rỗng
Dưới đây là code của mình viết theo thuật toán trên:
#include <iostream>
#include <string.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
#define SIZE 100
const int TOAN_TU = 1;
const int TOAN_HANG = 0;
int LayDoUuTien(char toantu); // Ham tra ve do uu tien cua toan tu
//** Ham xu ly stack **//
char Top(char stack[]); //Tra ve phan tu dau tien trong stack nhung khong xoa khoi stack
void Push(char phantu, char stack[]); //Dat 1 phan tu vao stack
char Pop(char stack[]); //Lay phan tu dau tien ra khoi stack
/* Ham noi 1 ky tu vao cuoi chuoi.*/
void ConCat(char kytu, char array[]);
/*
* Ham kiem tra ky tu elem co phai la toan tu khong?
* Tra ve 1 neu elem la toan tu.
* Nguoc lai tra ve 0.
*/
int LoaiPhanTu(char elem);
/**
* Chuyen 1 chuoi infix sang chuoi postfix
*/
void InfixToPostFix(char infix[], char postfix[]);
/*
* Tinh gia tri postfix.
* @param postfix[]: chuoi chua postfix
*/
float TinhGiaTriBieuThuc(char postfix[]);
/**
* Tinh gia tri cua phep toan 2 ngoi
*/
float TinhGiaTri(char toantu, float val1, float val2);
int main()
{
char infix[SIZE];
char postfix[SIZE];
//xoa vung nho chua postfix
strcpy(infix, "");
cout<<"note: \n";
cout<<" chi nhap toan tu tu 0 den 9\n";
cout << "nhap bieu thuc:";
cin >> infix;
InfixToPostFix(infix, postfix);
cout << "Postfix: " << postfix <<endl;
cout <<"Gia tri: ";
cout <<TinhGiaTriBieuThuc(postfix);
getch();
return 0;
}
void InfixToPostFix(char infix[], char postfix[])
{
char stack[SIZE];
strcpy(postfix, "");
strcpy(stack, "");
int len = strlen(infix);
for (int i = 0; i < len; i++)
{
char curChar = infix[i];
if (LoaiPhanTu(curChar) == TOAN_TU)
{
int rank1 = LayDoUuTien(curChar);
int rank2 = LayDoUuTien(Top(stack));
if (rank1 > rank2)
{
Push(curChar, stack);
} else
{
//Lay cac toan tu co do uu tien thap hon ra khoi stack
//va bo vao postfix
while (rank1 <= rank2)
{
if (Top(stack) == ' ')
break;
//lay phan tu tu` stack bo vao postfix
ConCat(Pop(stack), postfix);
//Kiem tra phan tu ke tiep trong stack
rank2 = LayDoUuTien(Top(stack));
}
Push(curChar, stack);
}
} else if (curChar == '(')
{
Push(curChar, stack);
} else if (curChar == ')')
{
char temp = Pop(stack);
while (temp != '(')
{
ConCat(temp, postfix);
temp = Pop(stack);
}
} else //toan hang
{
ConCat(curChar, postfix);
}
}
//lay nhung phan tu con lai trong stack
while (Top(stack) != ' ')
{
ConCat(Pop(stack), postfix);
}
}
int LoaiPhanTu(char elem)
{
if (elem == '+' || elem == '-' || elem == '*' || elem == '/')
{
return TOAN_TU;
}
return TOAN_HANG;
}
int LayDoUuTien(char toantu)
{
int iRes = -1;
switch (toantu)
{
case '*':
case '/':
iRes = 5;
break;
case '+':
case '-':
iRes = 4;
break;
default:
iRes = 0;
}
return iRes;
}
char Top(char stack[])
{
int len = strlen(stack);
if (len > 0)
{
return stack[len-1];
}
return ' '; // neu stack rong, tra ve ky tu trong
}
char Pop(char stack[])
{
int len = strlen(stack);
if (len > 0)
{
char cRes = stack[len-1];
stack[len-1] = '\0';
return cRes;
}
return ' ';
}
void Push(char phantu, char stack[])
{
int len = strlen(stack);
stack[len] = phantu;
stack[len+1] = '\0';
}
void ConCat(char kytu, char array[]) {
Push(kytu, array);
}
float TinhGiaTriBieuThuc(char postfix[]) {
float stackGiaTri[SIZE];
int dinh = -1; // vi tri di?nh cua stack
int len = strlen(postfix);
for (int i = 0; i < len; i++)
{
char curChar = postfix[i];
if (LoaiPhanTu(curChar) == TOAN_HANG) {
char ss[2];
ss[0] = curChar;
ss[1] = '\0';
float val = atof(ss);
dinh++;
stackGiaTri[dinh] = val;
}
else if (LoaiPhanTu(curChar) == TOAN_TU) {
float val2 = stackGiaTri[dinh];
dinh--;
if (dinh < 0) {
cout << "Bieu thuc co loi.";
exit(-1);
}
float val1 = stackGiaTri[dinh];
float val3 = TinhGiaTri(curChar, val1, val2);
stackGiaTri[dinh] = val3;
}
}
if (dinh > 0)
{
cout << "Bieu thuc khong dung";
exit(-1);
}
return stackGiaTri[dinh];
}
float TinhGiaTri(char toantu, float val1, float val2)
{
float fRes = 0;
switch (toantu)
{
case '*':
fRes = val1 * val2; break;
case '/':
{
if (val2 == 0)
{
cout << "Loi chia cho 0"; exit(-2);
}
fRes = val1 / val2; break;
}
case '+':
fRes = val1 + val2; break;
case '-':
fRes = val1 - val2; break;
break;
}
return fRes;
}
