code:
// asst3v1.cpp fall 2006 ALG starts from straray.cpp ch.7
// array of strings
#include <iostream>
#include <iomanip> //for setw function to format output
#include "string.h"
#include <math.h>
//standard namespace
using namespace std;
const int LMAX = 50; //maximum number of infix strings in array
const int NMAX = 30; //maximum size of each infix string
const int LSIZE = 5; //number of actual infix strings in array
const int MAXSTACK = 100;
//array of infix strings
char infix[LMAX][NMAX] = { "A+B-C",
"(A+B)*(C-D)",
"A$B*C-D+E/F/(G+H)",
"((A+B)*C-(D-E))$(F+G)",
"A-B/(C*D$E)" };
char postfix[NMAX][LMAX] = { };
float symval[8] = { 3, 1, 2, 5, 2, 4, -1, 3 };
struct OPERATOR_STACK
{
int top;
char item[MAXSTACK];
};
struct OPERAND_STACK
{
int top;
float item[MAXSTACK];
};
OPERATOR_STACK opstk; //declare variable opstk of OPERATOR_STACK
OPERAND_STACK opndstk; //declare variable opndstk of OPERATOR_STACK
char pfx[NMAX];
char ifx[NMAX];
int infixindex;
float pfval[NMAX] = {};
bool empty( OPERATOR_STACK& );
bool empty_oprnd( OPERAND_STACK& );
bool Oprnd( char );
bool Prcd( char, char );
void Pop( char&, OPERATOR_STACK& );
void Convert( char in[NMAX], char out[NMAX] );
void push( char, OPERATOR_STACK& );
void pushopr( float, OPERAND_STACK& );
float Popopr( float&, OPERAND_STACK& );
float Oper( char symb, float, float );
float Expon( float, float );
float Eval( char in[NMAX], OPERAND_STACK& opndstk );
int main()
{
opndstk.top = -1;
opstk.top = -1;
cout << endl << endl;
printf("%-25s%-25s%-25s\n", "Infix Expression", "Postfix Expression", "Final Value");
for ( int j=0; j < LSIZE; j++)
{
strcpy_s(ifx, infix[j]);
infixindex=j;
Convert( ifx, pfx );
strcpy_s( postfix[j], pfx);
pfval[j] = Eval( postfix[j], opndstk );
}
/****************************************************************************
PRINT OUT THE INFIX EXPRESSIONS
****************************************************************************/
cout << endl << endl;
for(int j=0; j<LSIZE; j++) //display name strings & corresponding weights
{
printf("%-25s%-25s%-25f\n", infix[j], postfix[j], pfval[j] );
}
cout << endl << endl;
system("pause");
return 0;
}
/****************************************************************************
CONVERT INFIX EXPRESSION TO POSTFIX NOTATION
****************************************************************************/
void Convert( char Infix[NMAX], char Postfix[NMAX] )
{
OPERATOR_STACK opstk;
opstk.top = -1;
char Pfx[LMAX] = {""};
char sym;
char topsym;
int i;
int j;
i=0;
for ( j = 0; j < ( strlen(Infix) ); j++ )
{
sym = Infix[j];
if ( Oprnd( sym ) )
{
Pfx[i] = sym;
i++;
}
else
{
while ( ( opstk.top != -1 ) && ( Prcd( opstk.item[opstk.top], sym ) ) )
{
Pop( topsym, opstk );
//topsym = opstk.top;
Pfx[i] = topsym;
i++;
}
if ( sym == ')' && opstk.item[opstk.top] == '(' )
{
Pop( sym, opstk );
}
else
{
push( sym, opstk );
}
}
}
while ( !empty( opstk ) )
{
Pop( topsym, opstk );
//topsym = opstk.top;
Pfx[i] = topsym;
i++;
}
strcpy( Postfix, Pfx );
}
/****************************************************************************
EVALUATE THE POSTFIX EXPRESSION
****************************************************************************/
float Eval( char expr[NMAX], OPERAND_STACK& oprndstk )
{
float opnd1;
float opnd2;
char symb;
float sym;
int position;
float value;
float eval;
opndstk.top = 0;
position = 0;
symb = expr[position];
do
{
if ( Oprnd( symb ) ) //function call 'is it an operand?'
{
value = symval[ symb - 'A'];
pushopr( value, oprndstk );
}
else // it is an 'operator'
{
opnd2 = Popopr( sym, oprndstk);
opnd1 = Popopr( sym, oprndstk);
value = Oper( symb, opnd1, opnd2 );
pushopr( value, oprndstk );
}
if ( position < MAXSTACK )
{
position++;
symb = expr[position];
}
else
{
symb = ' ';
}
}
while ( symb != 0 );
eval = Popopr( sym, oprndstk );
return eval;
}
/*********************************************
Is the stack empty?
*********************************************/
bool empty( OPERATOR_STACK& oprstk )
{
if (oprstk.top == -1) return true;
return false;
}
/*********************************************
Is the stack empty?
*********************************************/
bool empty_oprnd( OPERAND_STACK& operand_stk )
{
if (operand_stk.top == -1) return true;
return false;
}
/*********************************************
Push a Operator onto the stack
**********************************************/
void push( char opr, OPERATOR_STACK& oprstk )
{
oprstk.top++;
oprstk.item[oprstk.top]=opr;
}
/*********************************************
Push a Operand onto the stack
**********************************************/
void pushopr( float oprnd, OPERAND_STACK& oprndstk )
{
oprndstk.top++;
oprndstk.item[oprndstk.top]=oprnd;
}
/*********************************************
Operations
*********************************************/
float Oper( char symb, float op1, float op2 )
{
float anwser;
switch( symb )
{
case '+':
anwser = op1 + op2;
break;
case '*':
anwser = op1 * op2;
break;
case '-':
anwser = op1 - op2;
break;
case '/':
anwser = op1 / op2;
break;
case '$':
anwser = Expon( op1, op2);
break;
}
return anwser;
}
/*********************************************
Is it an Operand?
*********************************************/
bool Oprnd( char symb )
{
if (isupper(symb)) return true;
return false;
}
/*********************************************
Pop the top Operator from the stack
*********************************************/
void Pop( char& sym, OPERATOR_STACK& oprstk )
{
sym = oprstk.item[oprstk.top];
oprstk.item[oprstk.top] = 0;
oprstk.top--;
}
/*********************************************
Pop the top Operand from the stack
*********************************************/
float Popopr( float& sym, OPERAND_STACK& oprndstk )
{
sym = oprndstk.item[oprndstk.top];
oprndstk.item[oprndstk.top] = 0;
oprndstk.top--;
return sym;
}
/*********************************************
Exponate Calculations
*********************************************/
float Expon( float operator_1, float operator_2 )
{
float val;
//makes the op_1 to the op_2 = val
val = pow( operator_1, operator_2 );
return val;
}
/*********************************************
Precendence Function
*********************************************/
bool Prcd( char top, char symbol )
{
switch( top )
{
switch( symbol )
{
case '+': return true;
break;
case '*': return false;
break;
case '-': return true;
break;
case '/': return false;
break;
case '$': return false;
break;
case '(': return false;
break;
case ')': return true;
break;
}
break;
case '*':
switch( symbol )
{
case '+': return true;
break;
case '*': return true;
break;
case '-': return true;
break;
case '/': return true;
break;
case '$': return false;
break;
case '(': return false;
break;
case ')': return true;
break;
}
break;
case '-':
switch( symbol )
{
case '+': return true;
break;
case '*': return false;
break;
case '-': return true;
break;
case '/': return false;
break;
case '$': return false;
break;
case '(': return false;
break;
case ')': return true;
break;
}
break;
case '/':
switch( symbol )
{
case '+': return true;
break;
case '*': return true;
break;
case '-': return true;
break;
case '/': return true;
break;
case '$': return false;
break;
case '(': return false;
break;
case ')': return true;
break;
}
break;
case '$':
switch( symbol )
{
case '+': return true;
break;
case '*': return true;
break;
case '-': return true;
break;
case '/': return true;
break;
case '$': return true;
break;
case '(': return false;
break;
case ')': return true;
break;
}
break;
case '(': return false;
break;
}
}