**Solution**

**Basic Calculator II** https://leetcode.com/problems/basic-calculator-ii/

**Algorithm**

- Examples to run: 14-3/2
- 1-3/2+1
- Processing is left to right.
- if character is digit, scan the next number as num.
- if character is * or /, then pop the stack and scan the next number and complete the operation and push to stack.
- if character is -, then set sign to negative. Then the next scanned number will be negative and pushed on stack. Note we cannot prefetch next number here since 1-5/2 means 5/2 needs to be computed prior.
- Note the special treatment for division here. Python's division with negative numbers can be weird and hence we do the dance above.

```
class Solution(object):
def extract_num(self, expr, i):
num = 0
while i < len(expr) and (expr[i].isdigit() or expr[i].isspace()):
if expr[i].isdigit():
num = num*10 + int(expr[i])
i = i+1
return num, i
def calculate(self, expr):
"""
:type s: str
:rtype: int
"""
i, st = 0, []
negative_sign = False
operations = {
"+": lambda x,y:x+y,
"-": lambda x,y:x-y,
"/": lambda x,y: int(x/(float(y))),
"*": lambda x,y:x*y
}
while i < len(expr):
x = expr[i]
if x == "/" or x == "*":
op1 = st.pop()
op2, i = self.extract_num(expr, i+1)
st.append(operations[x](op1, op2))
elif x == "+" or x == "-":
if x == "-":
negative_sign = True
i = i+1
elif x.isspace():
i = i+1
else:
op, i = self.extract_num(expr, i)
if negative_sign:
op = op*-1
negative_sign = False
st.append(op)
return sum(st)
```