# 227. Basic Calculator II (Medium)

https://leetcode.com/problems/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.

## Solutions

``````class Solution {

public int calculate(String s) {
// format the s and split it to valid pieces.

// remove blank space
s = s.replace(" ", "").trim();

List<String> elements = new ArrayList<>();

// Firstly, split all the elements.

while (!s.isEmpty()) {
boolean findOp = false;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '+' || c == '-' || c == '*' || c == '/') {
findOp = true;

// trunk the string
s = s.substring(i + 1);

break;
}
}

if (!findOp) {

break;
}
}

// adopt a stack to keep elements for backtracking purpose
Stack<String> stack = new Stack<>();

// Secondly, process operands of * and /

for (int i = 0; i < elements.size(); i++) {

// right value of an expression if current element is a operand
String e1 = elements.get(i);

// pop out if meets higher priority operand
if (!stack.isEmpty() && (stack.peek().equals("*") || stack.peek().equals("/"))) {
// pop out the operand
String op = stack.pop();

// pop out left value for multiplication
String e2 = stack.pop();

// push back the result
if (op.equals("*")) {
stack.push("" + (Integer.valueOf(e1) * Integer.valueOf(e2)));
} else {
stack.push("" + (Integer.valueOf(e2) / Integer.valueOf(e1)));
}

continue;
}

// Push in low priority elements
}

int ans = 0;

// Finally, process operands of + and -

// Interpret the +,- expression from tail to head. But it is recommend to make it from head to tail.
String preE = stack.pop();
while (!stack.isEmpty()) {

String e = stack.pop();
if (e.equals("+")) {
ans += Integer.valueOf(preE);

continue;
}

if (e.equals("-")) {
ans -= Integer.valueOf(preE);

continue;
}

preE = e;
}

// Do not forget the first left element
ans = ans + Integer.valueOf(preE);

return ans;
}
}
``````