Comment on page

# 772.Basic-Calculator-III

## 题目描述

Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].
Some examples:
"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12

## 代码

Approach 1: Queue + Stack，遇到下一个sign时，再计算之前sign
• Queue: 存储所有的字符
• Stack 存储所有的num
class Solution {
public int calculate(String s) {
if (s == null || s.length() == 0) return 0;
Queue<Character> q = new LinkedList<>();
for (char c : s.toCharArray()) {
q.offer(c);
}
q.offer('+');
return cal(q);
}
private int cal(Queue<Character> q) {
char sign = '+';
Integer num = null; // 1 - 0 - 1
Stack<Integer> stack = new Stack<>();
while (!q.isEmpty()) {
char c = q.poll();
if (c == ' ') continue;
if (Character.isDigit(c)) {
if (num != null) {
num = 10 * num + c - '0';
} else {
num = c - '0';
}
} else if (c == '(') {
num = cal(q);
} else {
// + - * / )
if (sign == '+' && num != null) {
stack.push(num);
} else if (sign == '-') {
if (c == '-' && num == null) { // -1--1
c = '+'; // Negative + negative to positive
} else if(num != null){
stack.push(-num);
}
} else if (sign == '*' && num != null) {
stack.push(stack.pop() * num);
} else if (sign == '/' && num != null) {
stack.push(stack.pop() / num);
}
if (c == ')') {
break;
}
num = null;
sign = c;
}
}
int sum = 0;
while (!stack.isEmpty()) {
sum += stack.pop();
}
return sum;
}
}