Interview Question for Software Engineer at Microsoft:

First make up a Context Free Grammar for the expression. Next create an Abstract Syntax Tree using either LL(k) parsing or Recursive Decent Parsing. Then simply walk the leaf nodes of the AST and evaluate based on their parent functions.

There's an easier way that doesn't require a grammar.

Use two stacks: an operator stack, and an operand stack. Alternate between parsing operands and operators, pushing onto the appropriate stack as you go. Whenever you encounter an operator that has precedence less than or equal to the operator at the top of the operator stack, pop that operator and the topmost two operands, evaluate, and push the result onto the operand stack. You can treat the "end of string" as though it were an operator of the lowest precedence. When you are done, the operator stack should be empty, and the operand stack should contain one element, the result.

To handle parentheses, treat the left paren as though it were an operator, except that you'll always push it immediately without evaluating anything. Then treat the left paren as though it were an operator of the lowest precedence. This forces you to evaluate only within that paren group until you encounter its corresponding right paren, at which point you'll pop and evaluate until you get to the left paren.