Algorithm to Convert Infix Exp to Postfix Expression:
1. opstk = the empty stack;
2. while (not end of input){
3. symb = next input character;
4. if (symb is an operand)
add symb to the postfix string
5. else{
6. while (!opstk.empty () && prcd(opstk.Top(), symb)){
7. topsymb = opstk.pop();
8. add topsymb to the postfix string;
} /* end while*/
9. opstk.push(symb);
} /* end else*/
} /* end while*/
10. while (!opstk.empty()){
11. Topsymb = opstk.pop();
12. add topsymb to the postfix string;
} /* end while*/
9. if (opstk.empty () || symb != ‘)’)
opstk .push(symb);
else
topsymb = opstk.pop();
Precedence rules for parenthesis:
prcd(‘(’,op) = FALSE
Prcd(op,’(’) = FALSE
prcd(op,’)’) = TRUE
prcd(‘)’,op) = undefined
#include <iostream>
#include <process.h>
#include <string>
#include <math.h>
using namespace std;
bool prcd (char, char); //function declaration
template <class Type>
//stack class
class Stack
{
private:
Type *stack;
int top;
int Maxsize;
public:
Stack(int Max) //1-argument constructor
{
stack = new Type[Max];
top = -1;
Maxsize = Max;
}
//Boundary check, function to check weather stack is Empty or not.
bool isempty()
{
return (top==-1);
}
//Boundary check, function to check weather stack is Full or not.
bool isfull()
{
if (top == Maxsize)
return true;
else
return false;
}
//function to push value into stack
void push(Type val)
{
if (!isfull())
{
top++;
stack[top] = val;
}
else
{
cout << "stack overflow";
exit(1);
}
}
//function to pop out value from stack
Type pop()
{
if (!isempty())
{
int x = stack[top];
top--;
return x;
}
else
{
cout << "stack underflow";
exit(1);
}
}
//return top element of the stack
Type stacktop()
{
if (!isempty())
return stack[top];
else
{
cout << "stack underflow";
exit(1);
}
}
};
//Main Function
void main()
{
Stack<char> s(10);
string exp, post ;
cout << "Enter expression";
cin >> exp;
for (int i=0; i< exp.length(); i++)
{
char symb= exp[i];
if (symb >='A' && symb <= 'Z') // if alphabet
post.append(1,symb); // append string
else
{
while (!s.isempty() && prcd(s.stacktop(), symb)) // function call
{
char topsymb = s.pop();
post.append(1,topsymb);
}
if (s.isempty() || symb != ')')
s.push(symb);
else
s.pop();
}
}
while (!s.isempty())
{
char topsymb = s.pop();
post.append(1,topsymb);
}
cout << "Result is "<< post;
}
//Defination of the precedence checking function:
bool prcd (char top, char symb)
{
if (top == '(' || symb == '(')
return false;
if (symb == ')')
return true;
if (symb == '$')
return false;
if (top == '$')
return true;
if ((top== '*' ||top == '/') && ( symb== '*' || symb == '/'))
return true;
if (symb == '+' ||symb == '-')
return true;
else
return false;
return false;
}
Example Dry Run:
No comments:
Post a Comment