224.基本计算器
题目描述
给定一个字符串表达式s，计算并返回它的值。s只包含+，-，(，)，数字，空格。
+不用用作一元运算（比如+1和+(2+3)是无效的）；-可以用作一元运算（比如-1和-(2+3)是有效的）。
思路1
自己的思路。双栈，一个操作符栈，一个操作数栈。比较关键的点在于，在什么时候需要执行一次实际的运算？
- 在当前获取到一个数字，并且存在至少一个操作符时，需要运算。
- 在当前字符是
)时，说明括号内的已经计算完毕，需要和前一个操作数进行计算
为了方便的处理前方不存在第一个操作数的情况，我们用一个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.字符串解码
思路2
由于只存在+和-，我们考虑可以将括号进行展开。表达式中，除了第一个数字，其余每一个数字的前方，都一定会跟随一个+或者-。我们只需要维护，当前的符号是正还是负即可。
而一对括号()的出现，可能会改变括号内的运算符，所以，每当出现(时，我们就将当前的运算符压入栈，括号内部的运算符，都需要和栈顶的运算符做一个操作即可。
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';
}
}
227.基本计算器II
题目描述
给定一个字符串表达式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
394.字符串解码
题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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';
}
}
|