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;
// add integer value
elements.add(s.substring(0, i));
// add operand
elements.add(s.substring(i, i + 1));
// trunk the string
s = s.substring(i + 1);
break;
}
}
if (!findOp) {
elements.add(s);
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
stack.add(e1);
}
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;
}
}