## 227. Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains onlynon-negativeintegers,`+`,`-`,`*`,`/`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.

Thoughts: need to look back to know what is the operand value when encountered an operator. Hence need two variable: operator and operand.

1. With stack: using a stack to keep track of numbers and do the operation based on operators.
2. Without stack: only add current operand to the accumulative sum when encountered '+' or '-' since '*' and '/' has prioirty

Code: with a stack

``````class Solution {
public int calculate(String s) {
if(s == null || s.length() ==0) return 0;
int len = s.length();
Stack<Integer> stack = new Stack<Integer>();
int num = 0;
char sign= '+'; // equivalent to concatenate a '+' in front of s
for(int i = 0;  i < len ; i++){
// operand
if (Character.isDigit(s.charAt(i)))
num = 10 * num + s.charAt(i) - '0';
if ((!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ') || i == len - 1){
if(sign == '-'){
stack.push(-num);
}
if(sign == '+'){
stack.push(num);
}
if(sign == '*'){
stack.push(stack.pop()*num);
}
if(sign == '/'){
stack.push(stack.pop()/num);
}
sign = s.charAt(i);
num = 0;
}
}

int ans = 0;
for (int i: stack) ans += i;
return ans;
}
}
``````

Code: without a stack

``````class Solution {
public:
int calculate(string s) {
istringstream in('+' + s + '+');
long long total = 0, term = 0, n;
char op;
while (in >> op) {
if (op == '+' or op == '-') {
total += term;
in >> term;
term *= op == '+' ? 1 : -1;
} else {
in >> n;
if (op == '*')
term *= n;
else
term /= n;
}
}