Infix to Postfix Evaluation

[jbayne]

I have written a program that delt with taking an expression from file and evaluating that expression based on the order of operations. The expression is not quite evaluating the way that it should in longer expressions. If anyone can help, I would appreciated it more than anything

1) need a txt file labeled expression.txt, it can handle digits 1-9, left parens, right parens, and operators +-*/

2) the code: i will post if anyone can look at it

[_uj]

When an expression in infix notation is evaluated it's often turned into postfix (reverse polish) notation on the fly using a stack. There's lots of information, even complete code, available on the internet about how this (expression evaluation) can be done, like here

http://www.codeproject.com/cpp/rpnexpressionevaluator.asp

[cilu]

2) the code: i will post if anyone can look at it
If I were you I would have started with that.

[jbayne]

Here is my code....its really late so im going to hit the sack...i'll check out the link tomorrow....and if u have time, please check this out....im very greatful.....thanks




#include <iostream>
#include <fstream>

using namespace std;

const int MAX_ITEMS = 100;

/////////////////////////////////////////////////////////////////////////////////////////////

class StackTypeInt // for int stack
{
public:

StackTypeInt ();
bool IsEmpty () const;
bool IsFull () const;
void Push (int item);
void Pop ();
int Top () const;
int TopMinusOne () const;

private:

int top;
int items[MAX_ITEMS];
};

StackTypeInt::StackTypeInt ()
{
top = -1;
}

bool StackTypeInt::IsEmpty () const
{
return (top == -1);
}

bool StackTypeInt::IsFull () const
{
return (top == MAX_ITEMS - 1);
}

void StackTypeInt::Push (int newItem)
{
if (IsFull ())
{
cout << "Stack is full for INT Push function!" << endl;
exit (1);
}

top ++;
items[top] = newItem;
}

void StackTypeInt::Pop ()
{
if (IsEmpty ())
{
cout << "Stack is empty for INT Pop function!" << endl;
exit (1);
}
top --;
}

int StackTypeInt::Top () const
{
if (IsEmpty ())
{
cout << "Stack is empty for INT Top function!" << endl;
exit (1);
}
return items[top];
}

int StackTypeInt::TopMinusOne () const
{
if (IsEmpty ())
{
cout << "Stack is empty for INT TopMinusOne function!" << endl;
exit (1);
}
return items[top-1];
}

//////////////////////////////////////////////////////////////////////////////

const long LeftParen = 99990000;
const long RightParen = 88880000;
const long Multiply = 77770000;
const long Divide = 66660000;
const long Add = 55550000;
const long Subtract = 44440000;

/////////////////////////////////////////////////////////////////////////////

void InputExpression (ifstream& inFile, char expression[], int& expressionLength); // Reads the infix expression from a file
void IntegerStackConversion (char expression[], int expressionLength, StackTypeInt& ExpressionStack);
void CalcExpression (StackTypeInt& ExpressionStack, int expressionLength); //Calculates the postfix expression
int Precedence (int value); // Returns the precedence of the operator being evaluated
void EvaluateExpression (StackTypeInt& value, StackTypeInt& operatOr);

int main ()
{
ifstream inF;
char expressionArray [MAX_ITEMS];
StackTypeInt Expression;
int ArrayLength;
int i = 0;


inF.open ("expression.txt"); //opens the file that contains the expression
if (!inF)
{
cout << "**Cannot open expression.txt**" << endl;
return 1;
}

InputExpression (inF, expressionArray, ArrayLength); // call to read in the expression
IntegerStackConversion (expressionArray, ArrayLength, Expression);

CalcExpression (Expression, ArrayLength);

inF.close(); //closes the file



return 0;
}

void InputExpression (ifstream& inFile, char expression[], int& expressionLength) // Reads the infix expression from a file
{
int index = 0;
int i;

while (inFile) //reads in the expression
{
inFile >> expression [index];
index++;
}
expressionLength = index - 1;

cout << "Infix Expression from file into char array: ";

for (i = 0; i < expressionLength; i++) //echoes the expression to the console
{
cout << expression[i];
}
cout << endl << endl;
cout << "Expression Length: " << expressionLength << " characters" << endl << endl;

}

void IntegerStackConversion (char expression[], int expressionLength, StackTypeInt& ExpressionStack) //this function converts char numbers to int numbers
{
StackTypeInt ReverseInt;

int i = 0;

for (i = 0; i < expressionLength; i++)
{
//number push into ReverseInt
if (expression[i] == '0')
ReverseInt.Push (0);
if (expression[i] == '1')
ReverseInt.Push (1);
if (expression[i] == '2')
ReverseInt.Push (2);
if (expression[i] == '3')
ReverseInt.Push (3);
if (expression[i] == '4')
ReverseInt.Push (4);
if (expression[i] == '5')
ReverseInt.Push (5);
if (expression[i] == '6')
ReverseInt.Push (6);
if (expression[i] == '7')
ReverseInt.Push (7);
if (expression[i] == '8')
ReverseInt.Push (8);
if (expression[i] == '9')
ReverseInt.Push (9);

//parentheses pushed into ReverseInt
if (expression[i] == '(')
ReverseInt.Push (LeftParen);
if (expression[i] == ')')
ReverseInt.Push (RightParen);

//operators pushed into ReverseInt
if (expression[i] == '*')
ReverseInt.Push (Multiply);
if (expression[i] == '/')
ReverseInt.Push (Divide);
if (expression[i] == '+')
ReverseInt.Push (Add);
if (expression[i] == '-')
ReverseInt.Push (Subtract);
}

//stores the ReverseInt Stack into an ordered ExpressionStack
while (!ReverseInt.IsEmpty ())
{
ExpressionStack.Push(ReverseInt.Top ());
ReverseInt.Pop ();
}

/*
//test output function
while (!ExpressionStack.IsEmpty ())
{
cout << ExpressionStack.Top () << " ";
ExpressionStack.Pop ();
}
cout << endl;
*/

}

void CalcExpression (StackTypeInt& ExpressionStack, int expressionLength)
{
StackTypeInt valueStack;
StackTypeInt operatorStack;

while (!ExpressionStack.IsEmpty ())
{
if (ExpressionStack.Top () >= 0 && ExpressionStack.Top () <= 9)
{
valueStack.Push (ExpressionStack.Top ());
ExpressionStack.Pop ();
}

else if (ExpressionStack.Top () == LeftParen)
{
operatorStack.Push (ExpressionStack.Top ());
ExpressionStack.Pop ();
}

else if (ExpressionStack.Top () == Multiply || ExpressionStack.Top () == Divide ||
ExpressionStack.Top () == Add || ExpressionStack.Top () == Subtract)
{
if (operatorStack.IsEmpty ())
{
operatorStack.Push (ExpressionStack.Top ());
ExpressionStack.Pop ();
}
else if (Precedence (ExpressionStack.Top ()) > Precedence (operatorStack.Top ()))
{
operatorStack.Push (ExpressionStack.Top ());
ExpressionStack.Pop ();
}
else
{
while (!operatorStack.IsEmpty () && (Precedence (ExpressionStack.Top ()) <= Precedence (operatorStack.Top ())))
{
EvaluateExpression (valueStack, operatorStack);
operatorStack.Pop ();
}
operatorStack.Push (ExpressionStack.Top ());
ExpressionStack.Pop ();
}
}

else if (ExpressionStack.Top () == RightParen)
{
while (operatorStack.Top () != LeftParen)
{
EvaluateExpression (valueStack, operatorStack);
operatorStack.Pop ();
}
ExpressionStack.Pop ();
operatorStack.Pop ();
}

}

while (!operatorStack.IsEmpty ())
{
EvaluateExpression (valueStack, operatorStack);
operatorStack.Pop ();
}

// output the answer of the expression
while (!valueStack.IsEmpty ())
{
cout << valueStack.Top () << endl;
valueStack.Pop ();
}
}

int Precedence (int value) // Returns the precedence of the operator being evaluated
{
int level1 = 1; //levels determine precedence
int level2 = 2;
int level3 = 3;

if (value == Multiply)
{
return level3;
}
else if (value == Divide)
{
return level3;
}
else if (value == Add)
{
return level2;
}
else if (value == Subtract)
{
return level2;
}
else
{
return level1;
}
}

void EvaluateExpression (StackTypeInt& value, StackTypeInt& operatOr)
{
int temp = 0;
if (!value.IsEmpty ())
{
if (operatOr.Top () == Multiply)
{
temp = value.Top ()*value.TopMinusOne ();
while (!value.IsEmpty ())
{
value.Pop ();
}
}
else if (operatOr.Top () == Divide)
{
temp = value.TopMinusOne ()/value.Top ();
while (!value.IsEmpty ())
{
value.Pop ();
}
}
else if (operatOr.Top () == Add)
{
temp = value.TopMinusOne ()+value.Top ();
while (!value.IsEmpty ())
{
value.Pop ();
}
}
else if (operatOr.Top () == Subtract)
{
temp = value.TopMinusOne ()-value.Top ();
while (!value.IsEmpty ())
{
value.Pop ();
}
}
cout << temp;
value.Push (temp);
}
}

[BigEvil]

Well, your code isn't very elegant and it doesn't work for numbers > 9. You're not converting the expression to postfix, so it will be very difficult to evaluate it... So take _uj's advice and learn how to convert it to postfix.

btw, you can reduce and simplify your code by changing:
for (i = 0; i < expressionLength; i++)
{
//number push into ReverseInt
if (expression[i] == '0')
ReverseInt.Push (0);
if (expression[i] == '1')
ReverseInt.Push (1);
if (expression[i] == '2')
ReverseInt.Push (2);
if (expression[i] == '3')
ReverseInt.Push (3);
if (expression[i] == '4')
ReverseInt.Push (4);
if (expression[i] == '5')
ReverseInt.Push (5);
if (expression[i] == '6')
ReverseInt.Push (6);
if (expression[i] == '7')
ReverseInt.Push (7);
if (expression[i] == '8')
ReverseInt.Push (8);
if (expression[i] == '9')
ReverseInt.Push (9);
}
to

//number push into ReverseInt
if ( isdigit(expression[i] ) ) // isdigit() is in ctype.h
ReverseInt.Push(expression[i]-'0' );
and
f (value == Multiply)
{
return level3;
}
else if (value == Divide)
{
return level3;
}
else if (value == Add)
{
return level2;
}
else if (value == Subtract)
{
return level2;
}
else
{
return level1;
}
Its better to use switch when there are too many if - else if statements, makes your program much easier to understand
switch(value)
{
case Multiply:
case Divide:
return level3;
case Add:
case Subtract:
return level2;
default:
return level1;
}