# 772.Basic-Calculator-III

## ้ข็ฎๅฐๅ

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

}``````

Last updated