博文中会简要介绍Leetcode P0224题目分析及解题思路。
“Basic Calculator”是一道稍微难一点的题目，也是p0227的衍生题。这道题需要考虑括号分界符所导致的运算顺序的变化，不过我们依旧可以使用逆波兰算法。该算法的详解可以参考我的这篇博文：表达式求值“利器”：逆波兰算法详解
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 .
以下是Java的题解代码实现。
class Solution {
public int calculate(String s) {
return this.evaluate(this.generateRPN(s));
}
private int evaluate(List<String> rpn) {
Deque<Integer> stack = new LinkedList<>();
for (String s: rpn) {
switch (s) {
case "+":
stack.offerFirst(stack.pollFirst()+stack.pollFirst());
break;
case "-":
stack.offerFirst(-stack.pollFirst()+stack.pollFirst());
break;
default:
stack.offerFirst(Integer.parseInt(s));
break;
}
}
return stack.pollFirst();
}
private List<String> generateRPN(String s) {
List<String> ret = new ArrayList<>();
Deque<String> stack = new LinkedList<>();
int itr = 0;
while (itr < s.length()) {
char ch = s.charAt(itr);
switch (ch) {
case ' ':
break;
case '+':
if (!stack.isEmpty() && !"(".equals(stack.peekFirst()))
ret.add(stack.pollFirst());
stack.offerFirst("+");
break;
case '-':
if (!stack.isEmpty() && !"(".equals(stack.peekFirst()))
ret.add(stack.pollFirst());
stack.offerFirst("-");
break;
case '(':
stack.offerFirst("(");
break;
case ')':
if (!"(".equals(stack.peekFirst()))
ret.add(stack.pollFirst());
stack.pollFirst();
break;
default:
StringBuilder num = new StringBuilder();
int end = itr;
while (end < s.length() && Character.isDigit(s.charAt(end))) {
num.append(s.charAt(end));
++end;
}
itr = end-1;
ret.add(num.toString());
break;
}
++itr;
}
while (!stack.isEmpty())
ret.add(stack.pollFirst());
return ret;
}
}