Infix and Postfix Notation. Write a C++ program that will take any input infix c
ID: 3680777 • Letter: I
Question
Infix and Postfix Notation. Write a C++ program that will take any input infix computation consisting of (, ), +, -, *, / and positive numeric operands and convert it to postfix. Use a stack to do this program. Secondly, use the postfix form of the computation to actually calculate the result of applying the operators to the operands. In other words, use the output of the first part (a postfix string) to calculate the result.
The precedence order is as follows:
•* / = operators which have same precedence
•+ - = operators which have same precedence
•) = lower precedence than the operators
•( = lowest precedence
The computation should be input as a single string. Assume it is always correct with regard to format and parenthesis balancing, so you don't need to address errors.
Explanation / Answer
#include <iostream.h>
#include <string.h>
#include <ctype.h>
const int MAX = 50 ;
class infix
{
private :
char target[MAX], stack[MAX] ;
char *s, *t ;
int top, l ;
public :
infix( ) ;
void setexpr ( char *str ) ;
void push ( char c ) ;
char pop( ) ;
void convert( ) ;
int priority ( char c ) ;
void show( ) ;
} ;
infix :: infix( )
{
top = -1 ;
strcpy ( target, "" ) ;
strcpy ( stack, "" ) ;
l = 0 ;
}
void infix :: setexpr ( char *str )
{
s = str ;
strrev ( s ) ;
l = strlen ( s ) ;
* ( target + l ) = '' ;
t = target + ( l - 1 ) ;
}
void infix :: push ( char c )
{
if ( top == MAX - 1 )
cout << " Stack is full " ;
else
{
top++ ;
stack[top] = c ;
}
}
char infix :: pop( )
{
if ( top == -1 )
{
cout << "Stack is empty " ;
return -1 ;
}
else
{
char item = stack[top] ;
top-- ;
return item ;
}
}
void infix :: convert( )
{
char opr ;
while ( *s )
{
if ( *s == ' ' || *s == ' ' )
{
s++ ;
continue ;
}
if ( isdigit ( *s ) || isalpha ( *s ) )
{
while ( isdigit ( *s ) || isalpha ( *s ) )
{
*t = *s ;
s++ ;
t-- ;
}
}
if ( *s == ')' )
{
push ( *s ) ;
s++ ;
}
if ( *s == '*' || *s == '+' || *s == '/' ||
*s == '%' || *s == '-' || *s == '$' )
{
if ( top != -1 )
{
opr = pop( ) ;
while ( priority ( opr ) > priority ( *s ) )
{
*t = opr ;
t-- ;
opr = pop( ) ;
}
push ( opr ) ;
push ( *s ) ;
}
else
push ( *s ) ;
s++ ;
}
if ( *s == '(' )
{
opr = pop( ) ;
while ( ( opr ) != ')' )
{
*t = opr ;
t-- ;
opr = pop ( ) ;
}
s++ ;
}
}
while ( top != -1 )
{
opr = pop( ) ;
*t = opr ;
t-- ;
}
t++ ;
}
int infix :: priority ( char c )
{
if ( c == '$' )
return 3 ;
if ( c == '*' || c == '/' || c == '%' )
return 2 ;
else
{
if ( c == '+' || c == '-' )
return 1 ;
else
return 0 ;
}
}
void infix :: show( )
{
while ( *t )
{
cout << " " << *t ;
t++ ;
}
}
void main( )
{
char expr[MAX] ;
infix q ;
cout << " Enter an expression in infix form: " ;
cin.getline ( expr, MAX ) ;
q.setexpr( expr ) ;
q.convert( ) ;
cout << "The Prefix expression is: " ;
q.show( ) ;
}