CareerCup

Use a stack to store the operands, when you encounter an operator in the character list, you pop the top two stack elements and push back the resultant into the stack again. If the input expression is valid in terms of RPN, your result stack will always have one element at the end, which is the final answer.

def isOperand(op):
	if op == "+":
		return True
	elif op == "-":
		return True
	elif op == "*":
		return True
	elif op == "/":
		return True
	else:
		return False

def performOperation(n1, n2, op):
	if op == "+":
		return n1 + n2

	if op == "-":
		return n1 - n2

	if op == "*":
		return n1 * n2

	if op == "/":
		return n2/n1

def calculateRPN(expr):
	stack = []

	for char in expr:
		if not isOperand(char):
			stack.append(char)
		else:
			if len(stack) >= 2:
				first = int(stack.pop())
				second = int(stack.pop())

				stack.append(str(performOperation(first, second, char)))


	if stack:
		return stack.pop()


if __name__ == "__main__":
	s = raw_input().split(" ")
	print "The result of the given RPN is: ", calculateRPN(s)

Below solution uses Shunting-yard algorithm to convert common expression to Reverse Polish Notation (a.k.a Postfix Notation) and then calculates it. It has O(N) time and O(N) complexities and calculates expressions like:

"2 + (3*5 - 3) / 3"
"1 - 2*((3 - 5) / (-2)) + 2"
"1.5 - 2*((10 - 5) / (-2)) + 2.3"

import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class AdvanceCalculator {
		
	public double calc(String expression) {		
		String exp = prepareExpression(expression);
		Queue<String> queue = convertToRPN(exp);
		return calc(queue);		
	}
	
	// remove unnecessary symbols and deal with unary minuses
	private String prepareExpression(String expression) {
		String exp = expression.trim().replaceAll(" ","");
		
		// deal with unary '-'
		exp = exp.replaceAll("\\(-", "(0-");
		if (exp.charAt(0) == '-') {
			exp = "0-" + exp;
		}
		
		return exp;
	}
	
	// convert expression to postfix notation using Shunting-yard algorithm
	private Queue<String> convertToRPN(String exp) {
		Stack<String> stack = new Stack<>();
		Queue<String> queue = new LinkedList<>();
		StringTokenizer st = new StringTokenizer(exp, "+-*/()", true);
		while (st.hasMoreTokens()) {
			String e = st.nextToken();
			if (isOperator(e)) {				
				switch(e) {
					case "+": 
					case "-":
					case "*": 
					case "/": 	while (!stack.isEmpty() && 
									!stack.peek().equals("(") && 
									getOperatorPriority(e) <= getOperatorPriority(stack.peek())) {
										queue.add(stack.pop());
								}
							  stack.push(e);break;
					case ")": 	while(!stack.peek().equals("(")) {
									queue.add(stack.pop());
								}
								stack.pop(); break;
					case "(": 	stack.push(e);break;
				}				
			} else {
				queue.add(e);
			}
		}
		
		while (!stack.isEmpty()) {
			queue.add(stack.pop());
		}
		
		return queue;
	}
	
	// calculate postfix notation (a.k.a Reverse Polish Notation)
	private double calc(Queue<String> queue) {		
		Stack<Double> calc = new Stack<>();
		while (!queue.isEmpty()) {
			String e = queue.poll();
			if (isOperator(e)) {
				double v2 = calc.pop();
				double v1 = calc.pop();
				switch(e) {
					case "+": calc.push(v1 + v2);break;
					case "-": calc.push(v1 - v2);break;
					case "*": calc.push(v1 * v2);break;
					case "/": calc.push(v1 / v2);break;
				}
			} else {
				double value = Double.valueOf(e);
				calc.push(value);
			}
		}
		
		return calc.pop();
	}
	
	private boolean isOperator(String s) {
		switch(s) {
			case "+": return true;
			case "-": return true;
			case "*": return true;
			case "/": return true;
			case "(": return true;
			case ")": return true;
			default: return false;
		}
	}
	
	private int getOperatorPriority(String s) {
		switch(s) {
			case "+": return 1;
			case "-": return 1;
			case "*": return 2;
			case "/": return 2;
			default: return 0;
		}
	}
	
}

Was the phone interview 30 minutes on this one question? Seems long.

Hi Folks
Please, let me know if something was missed

import stack

def postfixEval(expression):
    operands = stack.Stack()
    for exp in expression:
        if exp in '0123456789':
            operands.push(exp)
        else:
            operator = exp
            operand2 = int(operands.pop())
            operand1 = int(operands.pop())
            result = doMath(operator, operand1, operand2)
            operands.push(result)

    return operands.pop()

def doMath(operator, operand1, operand2):
    operators = '*/+-'
    if operators.index(operator) == 0:
        return operand1 * operand2
    elif operators.index(operator) == 1:
        return operand1 // operand2
    elif operators.index(operator) == 2:
        return operand1 + operand2
    elif operators.index(operator) == 3:
        return operand1 - operand2

using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace AlgorithmsTests
{
    [TestClass]
    public class ReversePolishNotation
    {
        private int Calculate(string s)
        {
            if (string.IsNullOrEmpty(s))
                return 0;

            int result = 0;
            Queue<int> queue = new Queue<int>();
            string[] items = s.Split(new[] { ' ' });
            for (int i = 0; i < items.Length; i++)
            {
                int n;
                if (int.TryParse(items[i], out n))
                {
                    //n has the int value
                }
                else if (IsOperator(items[i]))
                {
                    int a = queue.Dequeue();
                    int b = queue.Dequeue();

                    n = Operate(items[i], a, b);
                }

                // enqueue the result or the number
                queue.Enqueue(n);
            }
            //return the last number form the queue
            return queue.Dequeue();
        }

        private int Operate(string o, int a, int b)
        {
            switch (o)
            {
                case "+":
                    return a + b;
                case "-":
                    return a - b;
                case "*":
                    return a * b;
                case "/":
                    return a / b;
                default:
                    throw new ApplicationException("Operator not suported.");
            }
        }

        private bool IsOperator(string s)
        {
            return s.Equals("+", StringComparison.OrdinalIgnoreCase) ||
                s.Equals("-", StringComparison.OrdinalIgnoreCase) ||
                s.Equals("*", StringComparison.OrdinalIgnoreCase) ||
                s.Equals("/", StringComparison.OrdinalIgnoreCase);
        }

        [TestMethod]
        public void RVN_Test()
        {
            Assert.AreEqual(0, Calculate(string.Empty));
            Assert.AreEqual(7, Calculate("3 4 +"));
            Assert.AreEqual(2, Calculate("6 3 /"));
            Assert.AreEqual(19, Calculate("3 5 * 4 +"));
            Assert.AreEqual(1, Calculate("10 2 / 4 -"));
        }
    }
}