给定一个字符串表达式s，计算并返回它的值。s只包含+，-，(，)，数字，空格。
+不用用作一元运算（比如+1和+(2+3)是无效的）；-可以用作一元运算（比如-1和-(2+3)是有效的）。
自己的思路。双栈，一个操作符栈，一个操作数栈。比较关键的点在于，在什么时候需要执行一次实际的运算？
)时，说明括号内的已经计算完毕，需要和前一个操作数进行计算为了方便的处理前方不存在第一个操作数的情况，我们用一个int变量实时保存当前运算的结果。
class Solution {
public int calculate(String s) {
Deque<Character> opStack = new LinkedList<>();
Deque<Integer> numStack = new LinkedList<>();
int sum = 0; // 保存当前的运算结果
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ' ') continue;
if (c == '(') {
opStack.push('(');
numStack.push(sum); // 把当前的运算结果暂存到操作数栈
sum = 0; // 清零
} else if (c == ')') {
opStack.pop(); // 把 ( 弹出
int a = numStack.isEmpty() ? 0 : numStack.pop();
char op = opStack.isEmpty() ? '+' : opStack.pop();
sum = calc(a, sum, op);
} else if (c == '+' || c == '-') {
opStack.push(c);
} else if (isDigit(c)) {
int num = 0;
int j = i;
while (j < s.length() && isDigit(s.charAt(j))) {
num = num * 10 + s.charAt(j) - '0';
j++;
}
i = j - 1;
if (opStack.isEmpty() || opStack.peek() == '(') sum = num;
else sum = calc(sum, num, opStack.pop());
}
}
return sum;
}
private int calc(int a, int b, char op) {
if (op == '+') return a + b;
return a - b;
}
private boolean isDigit(char c) {
return c >= '0' && c <= '9';
}
}
这个思路和之前做过的一道题目很类似：394.字符串解码
由于只存在+和-，我们考虑可以将括号进行展开。表达式中，除了第一个数字，其余每一个数字的前方，都一定会跟随一个+或者-。我们只需要维护，当前的符号是正还是负即可。
而一对括号()的出现，可能会改变括号内的运算符，所以，每当出现(时，我们就将当前的运算符压入栈，括号内部的运算符，都需要和栈顶的运算符做一个操作即可。
class Solution {
public int calculate(String s) {
Deque<Integer> ops = new LinkedList<>();
int res = 0;
int sign = 1; // 当前符号为+
ops.push(1); // 先压入一个+号
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ' ') continue;
if (c == '+') sign = ops.peek();
else if (c == '-') sign = -ops.peek(); // 和栈顶符号做一下运算
else if (c == '(') ops.push(sign); // 压入当前符号
else if (c == ')') ops.pop(); // 前一个(跟随的符号, 可以弹出栈了
else if (isDigit(c)) {
int num = 0;
int j = i;
while (j < s.length() && isDigit(s.charAt(j))) {
num = num * 10 + s.charAt(j) - '0';
j++;
}
i = j - 1;
res += sign * num; // 括号展开直接依次计算
}
}
return res;
}
private boolean isDigit(char c) {
return c >= '0' && c <= '9';
}
}
给定一个字符串表达式s，进行运算并求值。s中只包含+，-，*，/和空格。
双栈即可，运算符栈，只能优先级大的压优先级小的。反之需要将运算符出栈，并执行运算。
class Solution {
public int calculate(String s) {
Deque<Integer> nums = new LinkedList<>();
Deque<Character> ops = new LinkedList<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ' ') continue;
if (isDigit(c)) {
int j = i;
int num = 0;
while (j < s.length() && isDigit(s.charAt(j))) {
num = num * 10 + s.charAt(j) - '0';
j++;
}
i = j - 1;
nums.push(num);
} else {
while (!ops.isEmpty() && getPriority(c) <= getPriority(ops.peek())) {
int b = nums.pop();
int a = nums.pop();
nums.push(calc(a, b, ops.pop()));
}
ops.push(c);
}
}
while (!ops.isEmpty()) {
int b = nums.pop();
int a = nums.pop();
nums.push(calc(a, b, ops.pop()));
}
return nums.pop();
}
private int calc(int a, int b, char c) {
switch(c) {
case '*' : return a * b;
case '/' : return a / b;
case '+' : return a + b;
default : return a - b;
}
}
private int getPriority(char c) {
if (c == '*' || c == '/') return 2;
return 1;
}
private boolean isDigit(char c) {
return c >= '0' && c <= '9';
}
}
对比可以发现，两种计算器的题目，做法有一些区别。
第一题是用一个变量实时保存结果（对于解394这样的题很有用），而第二题则没有进行实时计算（经典的表达式求值的做法，需要考虑运算符优先级）。
follow up
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
输入：s = “3[a]2[bc]”
输出：“aaabcbc”
主要是需要用一个变量来保存当前已经拼接得到的字符串，然后每当遇到一个数字k，都会有k[。此时需要将先前拼接得到的字符串进行暂存，然后对[] 内的字符串处理完毕后，重复k次，拼接到先前的字符串上。使用StringBuilder 来避免String对象的频繁创建。
class Solution {
public String decodeString(String s) {
Deque<Integer> repeats = new LinkedList<>(); // 重复次数
Deque<StringBuilder> strings = new LinkedList<>(); // 暂存的字符串
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (isDigit(c)) {
int num = 0;
int j = i;
while (j < s.length() && isDigit(s.charAt(j))) {
num = num * 10 + s.charAt(j) - '0';
j++;
}
i = j - 1;
strings.push(sb);
repeats.push(num);
sb = new StringBuilder();
} else if (c == '[') continue;
else if(c == ']') {
StringBuilder temp = strings.pop();
int r = repeats.pop();
for (int j = 0; j < r; j++) temp.append(sb);
sb = temp;
} else {
sb.append(c);
}
}
return sb.toString();
}
private boolean isDigit(char c) {
return c >= '0' && c <= '9';
}
}