CareerCup

class expression
{
expression m_data;
public:
expression(int a):m_data(a){}
expression expression::operator+(expression a,expression b);
-,*,/
expression expression::operator()(expression a);
}

1)change it expression to binary tree which take the operator as the root of each nodes
2)traverse the tree with post-order.
3)traverse the result with stack.
when met the operator,pop up the topmost 2 values and calculate it,then push the result into the stack.

read the input character by character, first convert the infix expression into a postfix expression using a stack and adhering to precedence rules. Once the postfix expression is ready, evaluate the expression using a stack

aaah, this is a piece of cake!!! u can do this in O(n) time...
-create a postfix
-evaluate the result

if u need more email me at chrisogonas@yahoo.com

Chrisogonas's comment is quite silly, IMO. Practically useless(the comments before have alluded to postfix notation) and claiming that it is easy is idiotic.

Create postfix: how? Use the shunting yard algorithm.

Evaluation, you push onto stack till you see operator, in which case you pop the required number of arguments which the operator takes from the stack, evaluate and push back the answer on the stack.

1. construct (5 * 3) + (4 /2) into a binary tree, where the inner nodes are operators.
2. construct a post order of the tree: 5 3 * 4 2 / +
3. evaluate: push numbers in stack. when meets a operator, pop number of operands this operator needs from the stack, push the evaluation result into stack. Repeat until post order string is finished:
(1)push 5, push 3, meet *, which needs two operands. Pop, pop. Evaluate result is 15, push into the stack.
(2)push 4, push 2, meet /, which needs two operands. Pop, pop. Evaluate result is 2, push into the stack.
(3)meet +, which needs two operands. Pop, pop. Evaluate result is 17. push into the stack.
(4) end of the string. Pop. return as result.

The above algorithm assuming the post order traversal is correct, would lead to 15 being pushed into the stack followed by 4 and 2, and then the operator / being encountered.

At this point, 15 will be divided by 4. Not the right result.

The above algorithm assuming the post order traversal is correct, would lead to 15 being pushed into the stack followed by 4 and 2, and then the operator / being encountered.

At this point, 15 will be divided by 4. Not the right result.

Be careful this is not a data structure question, this is OO.
So
abstract Class Operation
class Multiplication
class Division
class Addition

all implementing the abstract method calculate()

So algo is :
Operation op1 = new Multiplication(5, 3)
Operation op2 = new Division(4, 2)
Operation op3 = new Addition(op1.calculate(), op2.calculate())

result = op3.calculate()

Use a composite design pattern:

class Expression {}

class CompositeExpression: public Expression {
   List<Expression> expression; 
   // This will have one expression, operator and another expression. The expression can be    operand/compositeexpression.
}

class Operand: Public Expression{}

class Operator: public Expression {}

To evaluate start breaking the compositeexpression. do expression operator expression. If the expression is composite, recursively try to evaluate it, till you reach operand.