# 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 head = 0;
int tail = 0;
bool nextCal = false;
while (tail <= s.size())
{
// Handle the number.
if ((tail > head) && (tail == s.size() || !isdigit(s[tail])))
{
int num = stoi(s.substr(head, tail - head));
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]);
}
head = tail + 1;
}
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 head = 0;
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])))
{
int curr = stoi(s.substr(head, tail - head));
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];
head = tail + 1;
}
tail++;
}
return res + prev;
}
};