## # 227. Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:

``````Input: "3+2*2"
Output: 7
``````

Example 2:

``````Input: " 3/2 "
Output: 1
``````

Example 3:

``````Input: " 3+5 / 2 "
Output: 5
``````

Note:

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

### # Solution

Approach 1: Stack.

Approach 2: Non-stack.

### # Code (Python)

Approach 2:

``````class Solution(object):
def calculate(self, string):
"""
:type s: str
:rtype: int
"""
string = [x for x in re.split('(\D)',string.strip()) if x and not re.match('\s', x)]
# i goes in steps of 2
result = int(string[0])
prev_val = result
i = 1
while i < len(string):
if string[i] == '+' or string[i] == '-':
prev_val = int(string[i+1]) if string[i] == '+' else -int(string[i+1])
result += prev_val
# if * or /, cancel prev result, add up and add prev result
elif string[i] == '*' or string[i] == '/':
result -= prev_val
if string[i] == '*':
prev_val *= int(string[i+1])
else:
# corrections for python division
correction = 0
if prev_val < 0 and prev_val % int(string[i+1]) != 0:
correction = 1
prev_val = int(prev_val // int(string[i+1])) + correction
result += prev_val
i += 2
return result
``````

### # Code (C++)

Approach 1:

``````// Stack.
class Solution {
private:
stack<int> st;
void tryCalculate() {
if (st.size() > 2)
{
int b = st.top();
st.pop();
char op = st.top();
st.pop();
int a = st.top();
st.pop();
switch (op)
{
case '+' : st.push(a + b); break;
case '-' : st.push(a - b); break;
case '*' : st.push(a * b); break;
case '/' : st.push(a / b); break;
}
}
}
public:
int calculate(string s) {
int tail = 0;
bool nextCal = false;
while (tail <= s.size())
{
// Handle the number.
if ((tail > head) && (tail == s.size() || !isdigit(s[tail])))
{
st.push(num);
if (nextCal || tail == s.size())
tryCalculate();
nextCal = false;
}
// Handle the non-number.
if (tail < s.size() && !isdigit(s[tail]))
{
if (s[tail] == '*' || s[tail] == '/')
{
st.push(s[tail]);
nextCal = true;
}
else if (s[tail] == '+' || s[tail] == '-')
{
tryCalculate();
st.push(s[tail]);
}
}
tail++;
}
tryCalculate();
return st.top();
}
};
``````

Approach 2:

``````// Non-stack.
// e.g., treat "3-2*2+1" as "0+3-2*2+1"
// init: prev = 0;
// for 0+3 : res += prev (0);  prev = 0; prev = prev + 3 (0 + 3)
// for 3-2 : res += prev (3);  prev = 0; prev = prev - 2 (0 - 2)
// for 2*2 : noop                      ; prev = prev * 2 (-2 * 2)
// for 2+1 : res += prev (-4); prev = 0; prev = prev + 1 (0 + 1)
// end: res += prev (1)
class Solution {
public:
int calculate(string s) {
int tail = 0;
int prev = 0;
char op = '+';
int res = 0;
while (tail <= s.size())
{
// Handle the number.
if ((tail > head) && (tail == s.size() || !isdigit(s[tail])))
{
if (op == '+' || op == '-')
{
res += prev;
prev = 0;
}
switch (op)
{
case '+' : prev = prev + curr; break;
case '-' : prev = prev - curr; break;
case '*' : prev = prev * curr; break;
case '/' : prev = prev / curr; break;
}
}
// Handle the non-number.
if (tail < s.size() && !isdigit(s[tail]))
{
if (s[tail] != ' ')
op = s[tail];