Example 1: infix to postfix program in c++
/*https://github.com/Sudhanshu1304/Stack-Application*/
using namespace std;
class Stack{
private:
char A[5];
int Size;
public:
int top;
Stack(){
top=-1;
Size=sizeof(A)/sizeof(char);
}
bool IsFull(){
if(top==Size-1){
return true;
}
else{
return false;
}
}
bool IsEmpty(){
if(top==-1){
return true;
}
else{
return false;
}
}
char peek(){
return A[top];
}
void Push(char val){
if (IsFull()==false){
top++;
A[top]=val;
}
else{
cout<<"\nThe Stack is Full"<<endl;
}
}
char Pop(){
if(IsEmpty()==false){
char temp=A[top];
A[top]='0';
top--;
return temp;
}
else{
return '-1';
}
}
void Show_Stack(){
for(int i=0;i<top+1;i++){
cout<<A[i];
}
}
};
int Search(char A){
string CHAR[]={"([","{)","]}","+-","*/","^$"};
int Size=(sizeof(CHAR)/sizeof(string));
for(int i=0;i<Size;i++){
if(A==CHAR[i][0]){
if(i+i>=6){
return i+i;
}
else{
return i+i+0;
}
}
else if(CHAR[i][1]==A){
if(i+i>=6){
return i+i;
}
else{
return i+i+1;
}
}
}
return -1;
}
void Display(char ch,string vari, Stack &s){
int Size=s.top+1;
cout<<"\n "<<ch<<" ";
s.Show_Stack();
for(int i=0;i<10-Size;i++){
cout<<" ";
}
cout<<vari<<endl;
}
int main(){
Stack STACK;
char temp;
string exp;//"A+B*C";
cout<<"Enter Your Expression :";
cin>>exp;
string out="";
cout<<"\n\nExpression Stack Postfix\n"<<endl;
for(int i=0;i<exp.size();i++){
temp=exp[i];
int ab=Search(temp);
if (ab!=-1){
/* If We ENCOUNTER CLOSING BRACKETS*/
if(ab<=5 && ab>=3){
while(Search(STACK.peek())>2){
char val=STACK.Pop();
out=out+val;
Display(temp,out,STACK);
}
STACK.Pop();
Display(temp,out,STACK);
}
/* Search Precedence*/
else{
if (Search(temp)>=0 && Search(temp)<=2){
STACK.Push(temp);
Display(temp,out,STACK);
}
/* If TOP < Temp */
else if(Search(STACK.peek())<ab){
STACK.Push(temp);
Display(temp,out,STACK);
}
else{
/* if STACK= +,* and temp= + then we have to remove two times */
while(Search(STACK.peek())>=ab){
char val=STACK.Pop();
out=out+val;
Display(temp,out,STACK);
}
STACK.Push(temp);
Display(temp,out,STACK);
}
}
}
/* If an Alphabet */
else{
out=out+temp;
Display(temp,out,STACK);
}
}
while(STACK.IsEmpty()==false){
char val=STACK.Pop();
out=out+val;
Display(temp,out,STACK);
}
cout<<"\n\nFINAL STRING : "<<out<<endl;
}
Example 2: Infix to postfix converstion using stack
/*
Infix to postfix conversion in C++
Input Postfix expression must be in a desired format.
Operands and operator, both must be single character.
Only '+' , '-' , '*', '/' and '$' (for exponentiation) operators are expected.
*/
using namespace std;
// Function to convert Infix expression to postfix
string InfixToPostfix(string expression);
// Function to verify whether an operator has higher precedence over other
int HasHigherPrecedence(char operator1, char operator2);
// Function to verify whether a character is operator symbol or not.
bool IsOperator(char C);
// Function to verify whether a character is alphanumeric chanaracter (letter or numeric digit) or not.
bool IsOperand(char C);
int main()
{
string expression;
cout<<"Enter Infix Expression \n";
getline(cin,expression);
string postfix = InfixToPostfix(expression);
cout<<"Output = "<<postfix<<"\n";
}
// Function to evaluate Postfix expression and return output
string InfixToPostfix(string expression)
{
// Declaring a Stack from Standard template library in C++.
stack<char> S;
string postfix = ""; // Initialize postfix as empty string.
for(int i = 0;i< expression.length();i++) {
// Scanning each character from left.
// If character is a delimitter, move on.
if(expression[i] == ' ' || expression[i] == ',') continue;
// If character is operator, pop two elements from stack, perform operation and push the result back.
else if(IsOperator(expression[i]))
{
while(!S.empty() && S.top() != '(' && HasHigherPrecedence(S.top(),expression[i]))
{
postfix+= S.top();
S.pop();
}
S.push(expression[i]);
}
// Else if character is an operand
else if(IsOperand(expression[i]))
{
postfix +=expression[i];
}
else if (expression[i] == '(')
{
S.push(expression[i]);
}
else if(expression[i] == ')')
{
while(!S.empty() && S.top() != '(') {
postfix += S.top();
S.pop();
}
S.pop();
}
}
while(!S.empty()) {
postfix += S.top();
S.pop();
}
return postfix;
}
// Function to verify whether a character is english letter or numeric digit.
// We are assuming in this solution that operand will be a single character
bool IsOperand(char C)
{
if(C >= '0' && C <= '9') return true;
if(C >= 'a' && C <= 'z') return true;
if(C >= 'A' && C <= 'Z') return true;
return false;
}
// Function to verify whether a character is operator symbol or not.
bool IsOperator(char C)
{
if(C == '+' || C == '-' || C == '*' || C == '/' || C== '$')
return true;
return false;
}
// Function to verify whether an operator is right associative or not.
int IsRightAssociative(char op)
{
if(op == '$') return true;
return false;
}
// Function to get weight of an operator. An operator with higher weight will have higher precedence.
int GetOperatorWeight(char op)
{
int weight = -1;
switch(op)
{
case '+':
case '-':
weight = 1;
case '*':
case '/':
weight = 2;
case '$':
weight = 3;
}
return weight;
}
// Function to perform an operation and return output.
int HasHigherPrecedence(char op1, char op2)
{
int op1Weight = GetOperatorWeight(op1);
int op2Weight = GetOperatorWeight(op2);
// If operators have equal precedence, return true if they are left associative.
// return false, if right associative.
// if operator is left-associative, left one should be given priority.
if(op1Weight == op2Weight)
{
if(IsRightAssociative(op1)) return false;
else return true;
}
return op1Weight > op2Weight ? true: false;
}
Example 3: python postfix conversion
"""
Author : ITVoyagers (itvoyagers.in)
Date :31st October 2019
Description : Program to show use of stack in infix to postfix conversion using python.
"""
class infix_to_postfix:
precedence={'^':5,'*':4,'/':4,'+':3,'-':3,'(':2,')':1}
def __init__(self):
self.items=[]
self.size=-1
def push(self,value):
self.items.append(value)
self.size+=1
def pop(self):
if self.isempty():
return 0
else:
self.size-=1
return self.items.pop()
def isempty(self):
if(self.size==-1):
return True
else:
return False
def seek(self):
if self.isempty():
return false
else:
return self.items[self.size]
def isOperand(self,i):
if i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
return True
else:
return False
def infixtopostfix (self,expr):
postfix=""
print('postfix expression after every iteration is:')
for i in expr:
if(len(expr)%2==0):
print("Incorrect infix expr")
return False
elif(self.isOperand(i)):
postfix +=i
elif(i in '+-*/^'):
while(len(self.items)and self.precedence[i]<=self.precedence[self.seek()]):
postfix+=self.pop()
self.push(i)
elif i is '(':
self.push(i)
elif i is ')':
o=self.pop()
while o!='(':
postfix +=o
o=self.pop()
print(postfix)
while len(self.items):
if(self.seek()=='('):
self.pop()
else:
postfix+=self.pop()
return postfix
s=infix_to_postfix()
expr=input('enter the expression ')
result=s.infixtopostfix(expr)
if (result!=False):
print("the postfix expr of :",expr,"is",result)