I am working on an assignment that does the following three things when a valid expression is provided:
1. Convert to postfix
2. convert to prefix
3. Evaluate expression.
I'm using stacks and Binary trees to do this and have been able to do the first two without a hick. I do, however, need help in evaluating the expression. Right now, what I'm doing is that i'm saving the expression and doing this:
int evaluateExpression(string expression)
{
Stacks<int> oprand;
Stacks<char> rator;
//If the expression is valid..
if(!expression.empty())
//loop through the expression
for(unsigned int i = 0; i < expression.length(); i++)
{
//if the current character is a number or operator or
//opening brace, push it into correct stack
if(isNumber(expression[i]))
oprand.push(expression[i] - '0');
else if(isOperator(expression[i]) || expression[i] == '(')
rator.push(expression[i]);
else if(expression[i] == ')') //else if it is a closing brace
{
char ratorPopped; //hold the popped operator
while((ratorPopped = rator.pop()) != '(') //loop until the opening brace is popped
{
int p1 = oprand.pop(), //store the first popped digit
p2 = oprand.pop(); //store the second popped digit
//do operation according to the operator
if(ratorPopped == '+')
oprand.push(p2 + p1); //push the result
else if(ratorPopped == '-')
oprand.push(p2 - p1);
else if(ratorPopped == '*')
oprand.push(p2 * p1);
else if(ratorPopped == '/')
oprand.push(p2 / p1);
}
//if the operator on top is a '*' or '/',
//evaluate it one more time
if(rator.top() == '*' || rator.top() == '/')
{
ratorPopped = rator.pop();
int p1 = oprand.pop(), p2 = oprand.pop();
if(ratorPopped == '*')
oprand.push(p2 * p1);
else if(ratorPopped == '/')
oprand.push(p2 / p1);
}
}
}
//after the expression has been pushed into the stacks
//evaluate it all untill the operator stack is empty
do
{
char ratorPopped = rator.pop();
int p1 = oprand.pop(), p2 = oprand.pop();
if(ratorPopped == '+')
oprand.push(p2 + p1);
else if(ratorPopped == '-')
oprand.push(p2 - p1);
else if(ratorPopped == '*')
oprand.push(p2 * p1);
else if(ratorPopped == '/')
oprand.push(p2 / p1);
}while(!rator.isEmpty());
//return the oprand.
return oprand.pop();
}
Now my code works fine for small expressions such as "2-3*(4+5)" but not for longer expressions such as "2+3*(4-5*(6+1)+7*2)"
I know i'm having a logic break down, and a brain freeze as well. So any and all help would be wonderful!