Calculator
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23My Solutions:
stack 储存的是括号前的符号。括号内的每一个数字加入result时，都要peek一下stack里的符号，相乘之后，再加入result。e.g. -(3 - 6) ， result -3+6
class Solution {
public int calculate(String s) {
s = s.replace(" ", ""); //去掉空格
int len = s.length(), sign = 1, res = 0, i = 0;
Stack<Integer> stack = new Stack<>();
stack.push(1); //一开始设置为正号
while (i < len) {
char c = s.charAt(i);
if (c == '+') {
sign = 1;
i++;
} else if (c == '-') {
sign = -1;
i++;
} else if (c == '(') {
stack.push(sign * stack.peek()); //stack里有（1, -1）
sign = 1;
i++;
} else if (c == ')') {
stack.pop();
i++;
} else {
int num = 0;
//判断是否超出边界或者不是digit(不再是一个数字)
while (i < len && Character.isDigit(s.charAt(i))) {
num = num * 10 + s.charAt(i) - '0';
i++;
}
res += num * sign * stack.peek();
}
}
return res;
}
}The expression string contains only non-negative integers, +, -, *, / operators and empty spaces. The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5My Solutions:
用一个sign的char储存之前的符号，用数字num储存数字，用stack储存所有可以相加的项。当遇见一个新符号，把num的数字做好相应的变化，压栈到stack里。最后把stack里的所有元素相加起来。
e.g., 3 * 2 - 5
碰到3： stack：空； sign = +； num = 3
碰到*： stack： 3； sign = *； num = 0
碰到2： num = 2；
碰到-： (stack pop出3，再push进6)stack: 6；sign = -; num = 0
碰到5：num = 5；
进入下一个if block，因为5是最后一个数字
stack：6， -5
class Solution {
public int calculate(String s) {
if (s == null || s.length() == 0) return 0;
Stack<Integer> stack = new Stack<>();
int num = 0; //num放在外面
char sign = '+'; //sign 储存的是数字之前的符号
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 如果当前字符是数字
if (Character.isDigit(c)) num = num * 10 + c - '0';
// 如果当前字符是+-*/, 先处理之前的数字
// 注意这里并不是else if，因为必须要处理最后一个数字
if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
if (sign == '+') stack.push(num); //stack只储存最后可以相加的项
else if (sign == '-') stack.push(-num); //把数字变为负号，stack只储存最后可以相加的项
else if (sign == '*') stack.push(stack.pop() * num); //把之前的数字pop出来，做乘运算，stack 只储存最后可以相加的项
else if (sign == '/') stack.push(stack.pop() / num); //把之前的数字pop出来，做除运算，stack 只储存最后可以相加的项
// 再更新新符号，以及重置num
sign = c; //符号更新成现在的char
num = 0;
}
}
//相加所有数字
int res = 0;
for (int i: stack) res += i;
return res;
}
}也可以优化一下，不用stack，直接用一个数字储存之前的数字
class Solution {
public int calculate(String s) {
int num = 0, res = 0, last = 0;
char sign = '+';
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) num = num * 10 + (c - '0');
if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
if (sign == '+') {
res += last;
last = num;
}
else if (sign == '-') {
res += last;
last = -num;
}
else if (sign == '*') {
last = last * num;
}
else if (sign == '/') {
last = last / num;
}
sign = c;
num = 0;
}
}
res += last;
return res;
}
}Basic Calculator III
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]
My Solutions:
和上一题的区别是既有加减乘除，又有括号。
用两个栈，一个存放数字，一个存放操作符。用evaluate方法解决计算问题，例如evaluate(op, num1, num2)，就表示num2 op(+-*/) num1。用isPrior判断哪个操作符优先级更高。
大概分以下情况：
走到一个数字，看下一位是否也是数字，如果是将他们拼接起来，压到栈里去
走到左括号，直接压入到操作符栈里去
走到右括号，从数字栈取2个数字，从操作符栈取1个操作符，进行运算，将结果压回到数字栈里去，重复这样的操作，直到操作符栈顶元素是左括号，这样说明这个括号内的就计算完成了。
走到操作符（+-*/)，查看操作符栈顶元素优先级是否低于当前操作符优先级，如果是的话，则跳过，不是的话，则进行evaluate运算。举个例子：当前操作符是"*"，栈顶是"+"，那么就是val1+val2*nextVal，这里肯定不能计算val1+val2，因为当前操作符的优先级更高。但是如果当前操作符是"+"，而操作符栈的栈顶元素是"*"，就可以经进行val1+val2的运算了，计算完的结果，放回数字栈里。（这里nextVal还有被遍历到）
public class Solution {
private int evaluate(char op, int b, int a) {
switch(op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
return 0;
}
private boolean isBeforeHigherPriority(char curr, char before) {
if (before == '(') return false;
if ((curr == '*' || curr == '/') && (before == '+' || before == '-')) return false;
return true;
}
public int calculate(String s) {
// 初始化两个栈：数字栈，操作符栈
Stack<Integer> stack = new Stack<>();
Stack<Character> ops = new Stack<>();
int num = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 如果是空格，直接跳过
if (c == ' ') continue;
// 如果是数字，那么继续查找下一个位置，直到拼接完整个数
if (Character.isDigit(c)) {
num = c - '0';
while (i < s.length() - 1 && Character.isDigit(s.charAt(i + 1))) {
num = num * 10 + (s.charAt(i + 1) - '0');
i++;
}
// 拼接完之后，压回数字栈里去
stack.push(num);
num = 0;
// 如果是左括号，直接压到操作符栈里去
} else if (c == '(') {
ops.push(c);
// 如果是右括号，则用evaluate计算，并将结果放回数字栈
// 直到操作符栈顶是左括号位置
} else if (c == ')') {
while (ops.peek() != '(') {
int val = evaluate(ops.pop(), stack.pop(), stack.pop());
stack.push(val);
}
ops.pop();
// 如果是操作符，且当前操作符优先级低于操作符栈顶的操作符优先级
// 则用evaluate计算一下结果，并将结果压回数字栈里
} else if (c == '+' || c == '-' || c == '*' || c == '/') {
while (!ops.isEmpty() && isBeforeHigherPriority(c, ops.peek())) {
int val = evaluate(ops.pop(), stack.pop(), stack.pop());
stack.push(val);
}
ops.push(c);
}
}
// 如果操作符栈不空，那么继续evaluate运算，并将结果放回数字栈
while(!ops.isEmpty()) {
int val = evaluate(ops.pop(), stack.pop(), stack.pop());
stack.push(val);
}
// 返回数字栈中的元素
return stack.pop();
}
}Last updated