CHUYỂN BIỂU THỨC TRUNG TỐ THÀNH HẬU TỐ VÀ TÍNH BIỂU THỨC HẬU TỐ SỬ DỤNG STACK VÀ QUEUE

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include<ctype.h>
#include<iostream>
#include <math.h>
#include <cstring>
#include<string.h>
#define MaxLength 100
#define MaxLength1 100
#define MaxLengthf 100

using namespace std;
typedef string ElementType;
typedef struct
{
ElementType Elements[MaxLength];
int Top_idx;
}Stack;
//====Tao ngan xep rong=====
void MakeNull_Stack(Stack *S)
{
S->Top_idx = MaxLength;
}
//===Kiem tra ngan xep rong====
int Empty_Stack(Stack S)
{
return(S.Top_idx == MaxLength);
}
//====Kiem tra ngan xep day===
int Full_Stack(Stack S)
{
return (S.Top_idx == 0);
}
//===Lay noi dung phan tu tai vi tri dinh cua ngan xep===
ElementType Top(Stack S)
{
if(!Empty_Stack(S))
return S.Elements[S.Top_idx];
else
{
printf("\nLoi! Stack rong");
}
}
//===Them phan tu vao ngan xep====
void Push(ElementType X, Stack *S)
{
if(Full_Stack(*S))
printf("\nloi! Stack day khong the them");
else{
S->Top_idx = (S->Top_idx - 1);
//Giam Top 1 don vi (Cho Top chi dden phan tu ke)*/
S->Elements[S->Top_idx] = X;
//Bo phan tu moi voi dau ngan xep
}
}
//Xoa phan tu ra khoi ngan xep====
void Pop(Stack *S)
{
if(Empty_Stack(*S))
printf("\nLoi ! Stack rong");
else
{
S->Top_idx = (S->Top_idx + 1);
//Tang Top 1 don vi (Cho Top chi lui xuong phan tu sau)
}
}
typedef float ElementTypef;
typedef struct
{
ElementTypef Elementsf[MaxLengthf];
int Topf_idx;
}Stackf;
//====Tao ngan xep rong=====
void MakeNull_Stackf(Stackf *U)
{
U->Topf_idx = MaxLengthf;
}
//===Kiem tra ngan xep rong====
int Empty_Stackf(Stackf U)
{
return(U.Topf_idx == MaxLengthf);
}
//====Kiem tra ngan xep day===
int Full_Stackf(Stackf U)
{
return (U.Topf_idx == 0);
}
//===Lay noi dung phan tu tai vi tri dinh cua ngan xep===
ElementTypef Topf(Stackf U)
{
if(!Empty_Stackf(U))
return U.Elementsf[U.Topf_idx];
else
{
printf("\nLoi! Stack rong");
}
}
//===Them phan tu vao ngan xep====
void Pushf(ElementTypef Y, Stackf *U)
{
if(Full_Stackf(*U))
printf("\nloi! Stack day khong the them");
else
{
U->Topf_idx = (U->Topf_idx - 1);
//Giam Top 1 don vi (Cho Top chi dden phan tu ke)*/
U->Elementsf[U->Topf_idx] = Y;
//Bo phan tu moi voi dau ngan xep
}
}
//Xoa phan tu ra khoi ngan xep====
void Popf(Stackf *U)
{
if(Empty_Stackf(*U))
printf("\nLoi ! Stack rong");
else
{
U->Topf_idx = (U->Topf_idx + 1);
//Tang Top 1 don vi (Cho Top chi lui xuong phan tu sau)
}
}
typedef string ElementType1;
typedef struct
{
ElementType1 Element[MaxLength1];
int Front, Rear;
}Queue;
//==Tao hang rong===
void MakeNull_Queue(Queue *Q)
{
Q->Front=-1;
Q->Rear=-1;
}
//Kiem tra hang rong
int Empty_Queue(Queue Q)
{
return Q.Front==-1;
}
//Kiem tra hang day
int Full_Queue(Queue Q)
{
return (Q.Rear-Q.Front+1)==MaxLength1;
}
//Them phan tu vao hang
void EnQueue(ElementType1 X, Queue *Q)
{
if(!Full_Queue(*Q))
{
if(Empty_Queue(*Q)) Q->Front=0;
if(Q->Rear==MaxLength1-1)
{
//Di chuyen tinh tien ra truoc Front -1 vi tri
for(int i =Q->Front;i<Q->Rear;i++)
Q->Element[i-Q->Front]=Q->Element[i];
//Xac dinh vi tri Rear moi
Q->Rear=MaxLength1 - Q->Front-1;
Q->Front=0;
}
//Tang Rear de luu noi dung moi
Q->Rear=Q->Rear+1;
Q->Element[Q->Rear]=X;
}
else printf("Loi: Hang day!");
}
//Xoa phan tu ra khoi hang
void DeQueue(Queue *Q)
{
if(!Empty_Queue(*Q))
{
Q->Front=Q->Front+1;
if(Q->Front>Q->Rear)
MakeNull_Queue(Q); //Dat hang rong
}
else printf("Loi: Hang rong!");
}
//Lay noi dung phan tu tai vi tri dau hang
ElementType1 Front(Queue Q)
{
return Q.Element[Q.Front];
}
//Lay noi dung phan tu tai vi tri cuoi hang
ElementType1 Rear(Queue Q)
{
return Q.Element[Q.Rear];
}
//Get phan tu cua chuoi nhap vao
string getPhanTu(string &bieuThuc)
{
int size = bieuThuc.size();
string kqua;
if(bieuThuc[0]=='('||bieuThuc[0]==')')
{

kqua.resize(1);
kqua = bieuThuc[0];
bieuThuc.erase(0,1);
return kqua;
}
if(bieuThuc[0]=='+'||bieuThuc[0]=='-'||bieuThuc[0]=='*'||bieuThuc[0]=='/'||bieuThuc[0]=='^')
{

kqua.resize(1);
kqua = bieuThuc[0];
bieuThuc.erase(0,1);
return kqua;
}
int i = 0;
while(i < size)
{
if(bieuThuc[i] >= '0' && bieuThuc[i] <= '9' )
{
kqua.resize(i+1);
kqua[i]=bieuThuc[i];
}
else
break;
i++;
}
bieuThuc.erase(0,i);
return kqua;
}
//Kiem tra phan tu la toan tu, toan hang hay dau ngoac
int KiemTraPhanTu(string Token)
{
if(Token == "+"||Token == "-"||Token == "*"||Token == "/"||Token == "^")
return 1;
else
{
if(Token == "("|| Token == ")")
return -1;
else
return 0;
}
}
//Do uu tien toan tu
int DoUuTien(string o)
{
if(o == "^")
return 3;
if(o == "*" || o == "/")
return 2;
if(o == "+" || o == "-")
return 1;
}
float Tinh(string dau, float a, float b)
{
if(dau == "+")
return a+b;
if(dau == "-")
return a-b;
if(dau == "*")
return a*b;
if(dau == "/")
return a/b;
if(dau == "^");
return pow(a,b);
}
void InfixtoPostfixAndCal(void)
{

Stack S;
Queue Q;
MakeNull_Stack(&S);
MakeNull_Queue(&Q);
string bieuThuc;
cout << "\nNhap Bieu Thuc Trung To: ";
getline(cin,bieuThuc);
while(!bieuThuc.empty())
{
string Token = getPhanTu(bieuThuc);
cout<<"\nToken = ";
cout<<Token<<endl;
if(KiemTraPhanTu(Token) == 0)
{
EnQueue(Token,&Q);
}
else
{
if(KiemTraPhanTu(Token) == 1)
{
while(!Empty_Stack(S))
{
if(KiemTraPhanTu(Top(S)) == 1 && DoUuTien(Top(S)) >= DoUuTien(Token))
{
EnQueue(Top(S),&Q);
Pop(&S);
}
else
break;
}
Push(Token, &S);
}
else
{
if(Token == "(")
Push(Token,&S);
else
{
if(Token == ")")
{
while(!Empty_Stack(S))
{
if(Top(S)!="(")
{
EnQueue(Top(S),&Q);
Pop(&S);
}
else
break;
}
Pop(&S);
}
}
}
}
}
while(!Empty_Stack(S))
{
EnQueue(Top(S),&Q);
Pop(&S);
}
printf("\nBieu Thuc Hau To: ");
Stackf U;
float kqua = 0;
MakeNull_Stackf(&U);
while(!Empty_Queue(Q))
{
string tmp = Front(Q);
DeQueue(&Q);
cout<<" "<<tmp;
if(KiemTraPhanTu(tmp) == 0) //tmp la toan hang
Pushf(stof(tmp),&U); //convert string to float
else
{
float num1 = Topf(U);
Popf(&U);
float num2 = Topf(U);
Popf(&U);
kqua = Tinh(tmp, num2, num1);
Pushf(kqua,&U);
}
}
printf("\n");
cout<<"\nKet qua la: "<<kqua;
printf("\n");
}

int main()
{
while(1)
{
InfixtoPostfixAndCal();
}
return 0;
}