infix to post fix and evaluation of the expression using stack using linked list
#include<iostream>
#include<string>
using namespace std;
template<typename T>
class Node
{
public:
Node *next;
T data;
};
template <class T>
class Stack{
Node<T> * top;
public:
Stack()
{
top=nullptr;
}
void Push(T X){
if(!IsFull()){
if(top==nullptr)
{
Node<T>*n=new Node<T>;
n->data=X;
n->next=nullptr;
top=n;
return;
}
Node<T> *n = new Node<T>;
n->data=X;
n->next=top;
top=n;
}}
T Pop(){
T data=top->data;
if(!IsEmpty()){
if(top->next==nullptr){
data=top->data;
top=nullptr;
return data;
}
Node<T>*n=top;
top=top->next;
delete n;
return data;
}
else{
cout<<"\nCant pop!! Stack is Empty\n";
}
}
bool IsEmpty(){
if(top==nullptr){
return true;
}
return false;
}
bool IsFull(){
Node<T>*temp=new Node<T>;
if(!temp){
return true;
}
delete temp;
return false;
}
void Print(){
if(!IsEmpty()){
Node<T>*temp=top;
if(temp==nullptr){
cout<<"\n!! Stack Is Empty\n";
}
while(temp!=nullptr){
cout<<""<<temp->data<<",";
temp=temp->next;
}
cout<<endl;
}
else{cout<<"\n!! Stack Is Empty\n";}
}
T Top(){
if(!IsEmpty()){
return top->data;
}
}
};
int main(){
Stack <char> Operator;
Stack <string> Postfix;
Stack <string> Result;
char Infix[100];
cout<<"Please Enter Infix Followed by Enter key(Max Size 100):";
cin.get(Infix,100);
char Operator_Value;
char ch;
string temp;
int size=strlen(Infix);
for(int i=0;i<size;i++)
{
if(Infix[i]=='+'||Infix[i]=='-'||Infix[i]=='*'||Infix[i]=='/'||Infix[i]=='('||Infix[i]==')')
{
if(Infix[i]=='*'||Infix[i]=='/'||Infix[i]=='(')
Operator.Push(Infix[i]);
else if(Infix[i]=='+'||Infix[i]=='-')
{
if(Operator.Top()=='*'||Operator.Top()=='/')
{
ch=Operator.Pop();
Operator_Value=ch;
while(ch!='('&& !Operator.IsEmpty())
{
temp.clear();
temp[0]=ch;
Postfix.Push(temp);
temp.clear();
ch=Operator.Pop();
}
Operator.Push(Infix[i]);
}
else
Operator.Push(Infix[i]);
}
else if(Infix[i]==')')
{
ch=Operator.Pop();
Operator_Value=ch;
while(Operator_Value!='(')
{
temp[0]=Operator_Value;
Postfix.Push(temp);
temp.clear();
ch=Operator.Pop();
Operator_Value=ch;
}
}
}
else
temp[0]=Infix[i];
Postfix.Push(temp);
temp.clear();
}
while(!Operator.IsEmpty())
{
ch=Operator.Pop();
Operator_Value=ch;
temp[0]=Operator_Value;
Postfix.Push(temp);
temp.clear();
}
Stack<string>RealPostfix;
while(!Postfix.IsEmpty())
{
temp.clear();
temp=Postfix.Pop();
ch=temp[0];
Operator_Value=ch;
temp.clear();
temp[0]=Operator_Value;
RealPostfix.Push(temp);
}
RealPostfix.Print();
cout<<endl;
return 0;
}
#include<string>
using namespace std;
template<typename T>
class Node
{
public:
Node *next;
T data;
};
template <class T>
class Stack{
Node<T> * top;
public:
Stack()
{
top=nullptr;
}
void Push(T X){
if(!IsFull()){
if(top==nullptr)
{
Node<T>*n=new Node<T>;
n->data=X;
n->next=nullptr;
top=n;
return;
}
Node<T> *n = new Node<T>;
n->data=X;
n->next=top;
top=n;
}}
T Pop(){
T data=top->data;
if(!IsEmpty()){
if(top->next==nullptr){
data=top->data;
top=nullptr;
return data;
}
Node<T>*n=top;
top=top->next;
delete n;
return data;
}
else{
cout<<"\nCant pop!! Stack is Empty\n";
}
}
bool IsEmpty(){
if(top==nullptr){
return true;
}
return false;
}
bool IsFull(){
Node<T>*temp=new Node<T>;
if(!temp){
return true;
}
delete temp;
return false;
}
void Print(){
if(!IsEmpty()){
Node<T>*temp=top;
if(temp==nullptr){
cout<<"\n!! Stack Is Empty\n";
}
while(temp!=nullptr){
cout<<""<<temp->data<<",";
temp=temp->next;
}
cout<<endl;
}
else{cout<<"\n!! Stack Is Empty\n";}
}
T Top(){
if(!IsEmpty()){
return top->data;
}
}
};
int main(){
Stack <char> Operator;
Stack <string> Postfix;
Stack <string> Result;
char Infix[100];
cout<<"Please Enter Infix Followed by Enter key(Max Size 100):";
cin.get(Infix,100);
char Operator_Value;
char ch;
string temp;
int size=strlen(Infix);
for(int i=0;i<size;i++)
{
if(Infix[i]=='+'||Infix[i]=='-'||Infix[i]=='*'||Infix[i]=='/'||Infix[i]=='('||Infix[i]==')')
{
if(Infix[i]=='*'||Infix[i]=='/'||Infix[i]=='(')
Operator.Push(Infix[i]);
else if(Infix[i]=='+'||Infix[i]=='-')
{
if(Operator.Top()=='*'||Operator.Top()=='/')
{
ch=Operator.Pop();
Operator_Value=ch;
while(ch!='('&& !Operator.IsEmpty())
{
temp.clear();
temp[0]=ch;
Postfix.Push(temp);
temp.clear();
ch=Operator.Pop();
}
Operator.Push(Infix[i]);
}
else
Operator.Push(Infix[i]);
}
else if(Infix[i]==')')
{
ch=Operator.Pop();
Operator_Value=ch;
while(Operator_Value!='(')
{
temp[0]=Operator_Value;
Postfix.Push(temp);
temp.clear();
ch=Operator.Pop();
Operator_Value=ch;
}
}
}
else
temp[0]=Infix[i];
Postfix.Push(temp);
temp.clear();
}
while(!Operator.IsEmpty())
{
ch=Operator.Pop();
Operator_Value=ch;
temp[0]=Operator_Value;
Postfix.Push(temp);
temp.clear();
}
Stack<string>RealPostfix;
while(!Postfix.IsEmpty())
{
temp.clear();
temp=Postfix.Pop();
ch=temp[0];
Operator_Value=ch;
temp.clear();
temp[0]=Operator_Value;
RealPostfix.Push(temp);
}
RealPostfix.Print();
cout<<endl;
return 0;
}
Comments
Post a Comment