Postfix,Prefix and evaluation of postfix code in Data Structures using stack
Post-fix + Prefix + Evaluation of Post-fix
Post-fix Algorithm
Infix to Postfix Conversion (Algorithm):
(Pseudocode)
1) Examine the next element in the input.
2) If it is operand, output it.
3) If it is opening parenthesis, push it on
stack.
4) If it is an operator, then
4.1) If stack is empty, push
operator on stack.
4.2) If the top of stack is opening
parenthesis, push operator on stack
4.3) If it has higher priority than
the top of stack, push operator on stack.
4.4) Else pop the operator from the
stack and output it, repeat step 4
5) If it is a closing parenthesis, pop operators
from stack and output them until an opening
parenthesis is encountered. pop and discard the opening
parenthesis.
6) If there is more input go to step 1
7) If there is no more input, pop the remaining
operators to output.
For example, Suppose we want to convert 2*3/(2-1)+5*3 into
Postfix form,
prefix Algorithm
The only difference in prefix function is the reverse working of for loop and change comes with inter-changing of closing and opening braces if condition. i made this code in very easy manner you can trace this code easily after watching it.
#include<iostream>
#include<string>
#include<ctype.h>
#include<cstring>
using namespace std;
#define size 100
struct Stack{
char expression[size];
char *output=new char[size];
int i = 0;
int j = -1;
int top = -1;
int count = 0;
bool isFull()
{
return(top == size - 1);
}
bool isEmpty()
{
return (top < 0);
}
void push(char v)
{
if (isFull())
{
cout << "We cannot add more data into Stack" << endl;
}
else
{
expression[++top] = v;
}
}
char pop()
{
if (isEmpty())
{
cout << "WE cannot remove anything because there is nothing" << endl;
}
else
{
char v = expression[top--];
return v;
}
}
char peek()
{
if (isEmpty())
{
cout << "There is nothing to show" << endl;
}
else
{
char v = expression[top];
return v;
}
}
int preci(char c)
{
if (c == '+' || c == '-')
{
return 1;
}
else if (c == '/' || c == '*' || c == '^')
{
return 2;
}
else
{
return -1;
}
}
void Postfix(char *e,int s) //Post-fix function
{
char c;
for (int i = 0; i < s; i++)
{
c = e[i];
if (c == '(' || c == '{' || c == '[')
{
push(c);
}
else if (c == '+' || c == '-')
{
if (preci(c)<preci(peek()))
{
char x = peek();
push(c);
output[++j] = x;
}
else
{
push(c);
}
}
else if (c == '/' || c == '*' || c == '^')
{
push(c);
}
else if (c == ')' || c == '}' || c == ']')
{
while (peek() != '('&&peek() != '{'&&peek() != '{'&&!isEmpty())
{
char x = peek();
pop();
output[++j] = x;
}
pop();
}
else
{
output[++j] = c;
}
}
while (!isEmpty())
{
output[++j] = pop();
}
}
void Prefix(char *e, int s) //Prefix function
{
char c;
for (int i = s; i>=0; --i)
{
c = e[i];
if (c == '(' || c == '{' || c == '[')
{
while (peek() != ')'&&peek() != '}'&&peek() != ']'&&!isEmpty())
{
char x = peek();
pop();
output[++j] = x;
}
pop();
}
else if (c == '+' || c == '-')
{
if (preci(c)<preci(peek()))
{
char x = peek();
push(c);
output[++j] = x;
}
else
{
push(c);
}
}
else if (c == '/' || c == '*' || c == '^')
{
push(c);
}
else if (c == ')' || c == '}' || c == ']')
{
push(c);
}
else
{
output[++j] = c;
}
}
while (!isEmpty())
{
output[++j] = pop();
}
}
void preShow()
{
int s=j-1;
cout << endl << endl;
cout << "Expression is:";
for (int z=s; z >=0; z--)
{
cout << output[z];
}
}
void postShow()
{
int s = j +1;
cout << endl << endl;
cout << "Expression is:";
for (int z = 0; z<s; z++)
{
cout << output[z];
}
}
void Evaluation(char *e, int s) //evaluation of post-fix
{
char a; int p, q; int count=0;
for (int i = 0; i < s; i++)
{
a = e[i];
if (a == '+')
{
if (count == 1)
{
cout << "Please enter the postfix expression" << endl;
system("pause");
}
else{
p = (int)pop() - '0';
q = (int)pop() - '0';
p = p + q;
push(p);
}
}
else if (a == '-')
{
if (count == 1)
{
cout << "Please enter the postfix expression" << endl;
system("pause");
}
else{
p = (int)pop() - '0';
q = (int)pop() - '0';
p = p - q;
push(p);
}
}
else if (a == '*')
{
if (count == 1)
{
cout << "Please enter the postfix expression" << endl;
system("pause");
}
else{
p = (int)pop() - '0';
q = (int)pop() - '0';
p = p * q;
push(p);
}
}
else if (a == '/')
{
if (count == 1)
{
cout << "Please enter the postfix expression" << endl;
system("pause");
}
else{
p = (int)pop() - '0';
q = (int)pop() - '0';
p = p / q;
push(p);
}
}
else if (a == '^')
{
if (count == 1)
{
cout << "Please enter the postfix expression" << endl;
system("pause");
}
else{
p = (int)pop() - '0';
q = (int)pop() - '0';
p = p ^ q;
push(p);
}
}
else
{
push(a);
count++;
}
}
if (count < 1)
{
cout << "PLease enter the integer and correct postfix expression" << endl;
system("pause");
}
else{
cout << endl << endl;
int x = pop();
cout << "Answer is:" << x << endl;
}
}
};
int main()
{
Stack s1;
int n;
cout << "Enter 1 to convert expression to postfix" << endl;
cout << "Enter 2 to perform evaluation of expression(expression should be in integer)" << endl;
cout << "Enter 3 conver expression to prefix" << endl;
cout << "Enter 4 to cancel the program" << endl;
cin >> n;
switch (n){
case 1:
{
char e[100];
cout << "Enter the expression to convert to postfix:";
cin >> e;
int s = strlen(e);
s1.Postfix(e, s);
s1.postShow();
break;
}
case 2:
{char e[100];
cout << "Enter the expression to convert to postfix:";
cin >> e;
int s = strlen(e);
s1.Evaluation(e,s);
break;
}
case 3:
{
char e[100];
cout << "Enter the expression to convert to postfix:";
cin >> e;
int s = strlen(e);
s1.Prefix(e, s);
s1.preShow();
break;
}
case 4:
{cout << "Thank you so much for your trust" << endl;
system("pause");
break;
}
default:
{
cout << "Option not found" << endl;
cout << endl << "please restart the program" << endl;
system("pause");
break;
}
}
getchar();
getchar();
return 0;
}
Comments
Post a Comment