最近准备系统的学习数据结构与算法，学习的时候想配合着 leetcode 刷题，这样会加深印象。在学习栈的时候，老师举了计算器实现的例子，我搜了一下 leetcode 刚好有这样的题，就想着自己实现一下吧。
leetcode 题目：
leetcode224leetcode227 实现一个基本计算器肯定是要有四则运算和括号运算的，实现一个这样的计算器自然就把这两题做出来了。
思路
这里参考了浙大 mooc 数据结构课程的栈的部分，首先是将常用的中缀表达式转换为后缀表达式，再将后缀表达式进行求值运算。
中缀表达式转为后缀表达式
用栈来存运算符，按顺序读取中缀表达式的每个对象，对每个对象按不同情况处理：
运算数：直接输出
左括号：压入栈
右括号：弹出并输出栈顶元素，直至遇到左括号停止，将左括号出栈丢弃
运算符：若优先级大于栈顶元素，则把它压栈；若优先级小于等于栈顶元素，则弹出并输出栈顶元素，再比较新的栈顶元素，直至优先级大于栈顶元素或者栈为空，再将该元素压入栈
处理完中序表达式后，将栈中还存留的运算符全部输出
例：
2*(9+1) -> 2 9 1 + *
2+9/3-5 -> 2 9 3 / + 5 –
后缀表达式求值
用栈来存取运算数，按顺序读取后缀表达式各项，对运算符和运算数做不同处理：
运算数：入栈
运算符：从栈中弹出两个运算数，根据运算符做运算求出结果后，将结果压栈
最后栈顶的元素就是表达式的值，此时栈中只有一个元素
代码：
转换表达式
// 将中缀转为后缀表达式，以空格分割运算数和运算符
private static String parseRPN(String s) {
// 用于返回的字符串
StringBuilder returnSb = new StringBuilder();
// 创建操作符栈
Stack<Character> stack = new Stack<Character>();
// 将字符串转换为字符数组，这样遍历字符串会快一些，使用 String.charAt() 会每次从头遍历
char[] cs = s.toCharArray();
// 开始从头处理中缀表达式的每个对象
int i = 0;
while (i < cs.length) {
// 匹配空格，将其舍弃
if (cs[i] == ‘ ‘) {
i++;
continue;
}
// 匹配数字，若匹配成功则将数字添加至 numberSb
StringBuilder numberSb = new StringBuilder();
while(i < cs.length&&cs[i]>=’0’&&cs[i]<=’9’){
numberSb.append(cs[i]);
i++;
}
if (numberSb.length()!=0) {// 若前面匹配到了数字，则 numberSb 长度必不为 0
returnSb.append(numberSb.append(‘ ‘));// 将 numberSb 添加空格后追加到 returnSb
continue;
}
// 匹配运算符
char symbol = cs[i];
// 遇到左括号直接压栈
if (symbol == ‘(‘) {
stack.push(symbol);
} else
// 遇到右括号，输出栈顶元素至左括号结束
if (symbol == ‘)’) {
while (stack.peek() != ‘(‘) {
returnSb.append(stack.pop() + ” “);
}
stack.pop();// 将左括号移出栈
} else
// 处理其他符号
// 优先级大于栈顶元素时，直接压栈
if (stack.isEmpty() || (symbol == ‘*’ || symbol == ‘/’) && (stack.peek() == ‘+’ || stack.peek() == ‘-‘)) {
stack.push(symbol);
} else {// 否则就输出栈顶元素至优先级大于栈顶元素或者遇到左括号或者栈为空，然后压栈
while (!stack.isEmpty()) {
if (stack.peek() == ‘(‘)
break;
if (!((symbol == ‘*’ || symbol == ‘/’) && (stack.peek() == ‘+’ || stack.peek() == ‘-‘))) {
returnSb.append(stack.pop() + ” “);
} else
break;
}
stack.push(symbol);
}
i++;
}
// 输出运算符栈的元素
while (!stack.isEmpty()) {
returnSb.append(stack.pop() + ” “);
}
return returnSb.toString();
}
后缀表达式求值
定义的几个 long 型变量是为了观察运行时间
public int calculate(String s) {
long time1 = System.currentTimeMillis();
// 操作数栈
Stack<Integer> stack = new Stack<Integer>();
// 将 s 转为后缀表达式，并转为字符数组
char[] cs = parseRPN2(s).toCharArray();
long time2 = System.currentTimeMillis();
int i = 0;
//tmpSb 用来临时存放数字，主要是考虑到数字不止一位
StringBuilder tmpSb = new StringBuilder();
while (i < cs.length) {
if (cs[i] == ‘ ‘) {// 遇到空格就把 tmpSb 转为数字并压入栈
if (tmpSb.length() != 0) {
stack.push(Integer.parseInt(tmpSb + “”));
tmpSb = new StringBuilder();
}
i++;
continue;
}
// 遇到数字就加在 tmpSb 后
if (cs[i] >= ‘0’ && cs[i] <= ‘9’) {
tmpSb.append(cs[i]);
i++;
continue;
}
// 不是空格也不是数字就是运算符，弹出两个数进行运算，注意这里弹出的第一个数为 b，第二个数才是 a，这里我一开始写错了
int b = stack.pop();
int a = stack.pop();
switch (cs[i]) {
case ‘+’:
stack.push(a + b);
break;
case ‘-‘:
stack.push(a – b);
break;
case ‘*’:
stack.push(a * b);
break;
case ‘/’:
stack.push(a / b);
break;
}
i++;
}
long time3 = System.currentTimeMillis();
System.out.println(“ 总耗时：” + (time3 – time1));
System.out.println(“ 转换后缀耗时：” + (time2 – time1));
System.out.println(“ 求值耗时：” + (time3 – time2));
// 最后在栈里的唯一一个元素就是要求的值
return stack.pop();
}
测试
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.next();
System.out.println(new Solution().calculate(s));
}
输入:19 * (2+8) 输出:
总耗时：44
转换后缀耗时：26
求值耗时：18
结果为：190
还有一个输入为 leetcode 测试用例，s 非常长，我写的这个方法也能在半秒之内得出结果，速度还是很快的。我之前写的一个转换后缀的方法由于大量的新建 StringBuilder，就导致了这个测试用例因为超时而未通过，大概是 7 秒左右，在这里我也贴一下代码，这里不提倡使用。
超时代码
private static String parseRPN2(String s) {
StringBuilder returnSb = new StringBuilder();
Stack<Character> stack = new Stack<Character>();
Pattern space = Pattern.compile(“\\s+”);
Pattern number = Pattern.compile(“\\d+”);
StringBuilder sb = new StringBuilder(s);
while (sb.length() != 0) {
Matcher spaceMatcher = space.matcher(sb);
if (spaceMatcher.lookingAt()) {
sb = new StringBuilder(sb.subSequence(spaceMatcher.end(), sb.length()));
continue;
}
Matcher numberMatcher = number.matcher(sb);
if (numberMatcher.lookingAt()) {
returnSb.append(numberMatcher.group() + ” “);
sb = new StringBuilder(sb.subSequence(numberMatcher.end(), sb.length()));
continue;
}
char symbol = sb.charAt(0);
if (symbol == ‘(‘) {
stack.push(symbol);
} else
if (symbol == ‘)’) {
while (stack.peek() != ‘(‘) {
returnSb.append(stack.pop() + ” “);
}
stack.pop();
} else
if (stack.isEmpty() || (symbol == ‘*’ || symbol == ‘/’) && (stack.peek() == ‘+’ || stack.peek() == ‘-‘)) {
stack.push(symbol);
} else {
while (!stack.isEmpty()) {
if (stack.peek() == ‘(‘)
break;
if (!((symbol == ‘*’ || symbol == ‘/’) && (stack.peek() == ‘+’ || stack.peek() == ‘-‘))) {
returnSb.append(stack.pop() + ” “);
} else
break;
}
stack.push(symbol);
}
sb = new StringBuilder(sb.subSequence(1, sb.length()));
}
while (!stack.isEmpty()) {
returnSb.append(stack.pop() + ” “);
}
return returnSb.toString();
}
结语
计算器的基本实现就是基于这样的方法，后面我在学习其他数据结构和算法时会继续分享，