Problem:

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2

" 2-1 + 2 " = 3

"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

Directly Calculation

Attention the sign

def calculate(self, s):
    res, num, sign, stack = 0, 0, 1, [1]
    for i in s+"+":
        if i.isdigit():
            num = 10*num + int(i)
        elif i in "+-":
            res += num * sign * stack[-1]
            sign = 1 if i=="+" else -1
            num = 0
        elif i == "(":
            stack.append(sign * stack[-1])
            sign = 1
        elif i == ")":
            res += num * sign * stack[-1]
            num = 0
            stack.pop()
    return res

Recursive Calculation

def calculateBracket(expression, leftStartIndex):  
    pos = leftStartIndex
    res = 0 
    sign = "+"
    while pos < len(expression) and expression[pos] != ")":
        tempRes = 0 
        if expression[pos] == "(":
            pos, tempRes = calculateBracket(expression, pos+1)
        else:
            if expression[pos].isdigit():
                while pos<len(expression) and expression[pos].isdigit():
                    tempRes = tempRes*10 + int(expression[pos])
                    pos += 1
            else:
                if expression[pos] == "+" or expression[pos] == "-":
                    sign = expression[pos]
                pos += 1
        if sign == "+":
            res += tempRes
        elif sign == "-":
            res -= tempRes
    return pos+1, res
pos, result  = calculateBracket(s, 0)
return result

Reverse Polish

def calculate(self, s):
    s = s.replace(' ', '')
    oper = {"+": lambda y, x: x + y, "-": lambda y, x: x - y}
    oper_stack, num_stack = [], []
    tmp = ''
    for c in s:
        if c.isdigit():
            tmp += c
            continue
        if tmp:
            num_stack.append(int(tmp))
            tmp = ''
        if c == '(':
            oper_stack.append(c)
        else:
            while oper_stack and oper_stack[-1] != '(':
                num_stack.append(oper[oper_stack.pop()](num_stack.pop(), num_stack.pop()))
            if c in oper:
                oper_stack.append(c)
            else:
                oper_stack.pop()
    if tmp:
        num_stack.append(int(tmp))
    while oper_stack:
        num_stack.append(oper[oper_stack.pop()](num_stack.pop(), num_stack.pop()))
    return num_stack[0]