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!

OK, I modified it such that it would use recurssion and evaluate the braces first and then push their result in the oprand.

this is the new code:

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]))
				rator.push(expression[i]);
			else if(expression[i] == '(') //else if it is a closing brace
			{
				i++;
				string bracedExpression = "";
				for(; expression[i] != ')'; i++)
				{
					bracedExpression += expression[i];
				}
				oprand.push(evaluateExpression(bracedExpression));
			}
		}

		//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();
}

Still I am not able to make head and tail :(

OK, so I was able to get a way to evaluate using the postfix expression:

int evaluateExpression(string expression)
{
	Stacks<signed int> oprand;

	int i,l,a,b,z, r;

	l= expression.length();

	for(i=0;i<l;i++)
	{
		if ( isNumber( expression[i] ) )
		{
			oprand.push(expression[i] - 48);
		}
		else if ( expression[i] == '*' || expression[i] == '+' || expression[i] == '/' || expression[i] == '%' || expression[i] == '-' )
		{
			a = oprand.pop( );
			b = oprand.pop( );

			switch( expression[i] )
			{
			case '+' : 
				r = b + a;
				cout << "r= " << b << "+" << a << "=" << r << endl;
				break;
			case '-' : 
				r = b - a; 
				cout << "r= " << b << "-" << a << "=" << r << endl;
				break;
			case '*' : 
				r = b * a; 
				cout << "r= " << b << "*" << a << "=" << r << endl;
				break;
			case '/' : 
				r = b / a;
				cout << "r= " << b << "/" << a << "=" << r << endl;
				break;
			}

			oprand.push(r);
		}
	}

	return oprand.pop();
}

The problem I'm facing now is that the subtraction operation is playing funny with me. If I have the expression 2-3*(4+5), i.e. postfix: 2345+*- the answer is correct: -25. But if I use this expression:
2+3*(4-5*(6+1)+7*2), the subtraction breaks at '4-5*(6+1)' and the answer is 137

Any suggestions?

Hi people,
I am a beginner in c++.Can you please help me out?
How to accept floating point number along with integers to perform arithmetc operations in c++ to develop a scientific calculator?

This article has been dead for over six months. Start a new discussion instead.