数据结构与算法 | LeetCode 224. Basic Calculator

space_scene

前面,我们学习了 栈的实现及其应用 ,今天我们基于栈,来实现一个简单的计算器功能。

简单计算器实现

Leetcode 224. Basic Calculator

实现一个能够对简单的表达式进行计算的基础计算器。

表达式字符串包含括号 (),加号(+),减号(-),非负整数以及空格(‘ ‘)。

Example 1:

1
2
Input: "1 + 1"
Output: 2

Example 2:

1
2
Input: " 2-1 + 2 "
Output: 3

Example 3:

1
2
Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

使用两个栈来实现

根据 栈的实现及其应用 中学到的表达式求值的解法:

编译器会使用两个栈来实现,一个栈用来保存操作数,另一个栈用来保存运算符。从左向右遍历表达式,遇到数字直接压入操作数栈,遇到操作符,就与运算符栈顶元素进行比较。

如果比运算符栈顶元素的优先级高,就将当前运算符压入栈;如果比运算符栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈的栈顶取 2 个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较。

下面是我根据上面思路,写出来的第一版实现,相比于网上巧妙的解题方法,确实复杂很多,在LeetCode的运行时间为 195 ms ,只超过了 8.14% 的提交记录 😅 。

思路

  1. 先对表达式进行校验,去除空格,并转化为ArrayList,如果按照一个字符一个字符去遍历的到,要是表达式中存在多位的整数,就行不通了。
  2. 对转化后的 ArrayList 进行遍历,遇到数字,直接压入操作数栈。
  3. 遇到操作符,则进行需要进行一系列的判断,特别是遇到括号的处理:
    1. 操作符栈为空的情况下,直接入栈;
    2. 比较 新的操作符操作符栈顶元素 的优先级,优先级高,则直接入栈。如果它们有一个或都是左括号,则直接入栈;
    3. 如果优先级低或相同,则对前面的表达式进行递归计算,将最后的结果压入操作数栈。之后,在递归调用自身,压入新的操作符。
  4. 遍历结束后,在对操作数站进行最后一次递归计算;
  5. 取出操作数栈的栈顶元素。

代码如下

里面用到的 LinkedStack 是我们前面自己实现的链表栈,当然使用 ArrayStack 也可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
package one.wangwei.leetcode.stack;

import one.wangwei.algorithms.datastructures.stack.IStack;
import one.wangwei.algorithms.datastructures.stack.impl.LinkedStack;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

/**
* 简单计算器实现
*
* @author https://wangwei.one
* @date 2019/1/18
*/
public class MyBasicCalculator {

private IStack<Integer> operand;
private IStack<String> operator;
private Set<String> highOperator;
private Set<String> lowOperator;
private Set<String> parentheses;
private Set<String> operatorSet;

public MyBasicCalculator() {
this.operand = new LinkedStack<>();
this.operator = new LinkedStack<>();

this.parentheses = new HashSet<>();
this.parentheses.add("(");
this.parentheses.add(")");

this.highOperator = new HashSet<>();
this.highOperator.add("*");
this.highOperator.add("/");

this.lowOperator = new HashSet<>();
this.lowOperator.add("+");
this.lowOperator.add("-");

this.operatorSet = new HashSet<>();
this.operatorSet.addAll(highOperator);
this.operatorSet.addAll(lowOperator);
this.operatorSet.addAll(parentheses);
}

/**
* 运算表达式
*
* @param s
* @return
*/
public int calculate(String s) {
if (s == null || s.isEmpty()) {
throw new RuntimeException("Expression Invalid! expr=" + s);
}

ArrayList<String> express = convertExpr(s);
for (String str : express) {
if (!operatorSet.contains(str)) {
operand.push(Integer.valueOf(str));
} else {
pushOperator(str);
}
}

// 对余下的操作数进行计算,得到最后的结果
operandCalcu();

return operand.pop();
}

/**
* 转换表达式
* <p>
* 1. 去除空格
* 2. 拆分出有效的数字
*
* @param expr
* @return
*/
private ArrayList<String> convertExpr(String expr) {
ArrayList<String> result = new ArrayList<>();
// remove empty spaces
String trimExpr = expr.replaceAll("\\s+", "");

String tmpIntStr = "";
for (Character ch : trimExpr.toCharArray()) {
String str = ch.toString();
if (operatorSet.contains(str)) {
if (!tmpIntStr.isEmpty()) {
result.add(tmpIntStr);
tmpIntStr = "";
}
result.add(str);
} else {
tmpIntStr = tmpIntStr + str;
}
}
if (!tmpIntStr.isEmpty()) {
result.add(tmpIntStr);
}
return result;
}

/**
* 运算符入栈
*
* @param operatorSign
*/
private void pushOperator(String operatorSign) {
String prevOperator = null;
if (!operator.empty()) {
prevOperator = operator.peek();
}
// 第一次入栈
if (prevOperator == null) {
operator.push(operatorSign);
} else {
if (")".equals(operatorSign) && "(".equals(prevOperator)) {
operator.pop();
return;
}
// 第一次以后入栈,先比较优先级,高优先级,则入栈
if (priority(operatorSign, prevOperator)) {
operator.push(operatorSign);
} else {
// 否则先对前面的表达式进行计算
operandCalcu();
pushOperator(operatorSign);
}
}
}

/**
* 从操作数栈取出两个操作数进行计算
*/
private void operandCalcu() {
if (operator.empty()) {
return;
}
String sign = operator.peek();
if ("(".equals(sign)) {
return;
}

sign = operator.pop();
int after = operand.pop();
int front = operand.pop();

int value = calcIntegers(front, after, sign);
operand.push(value);
operandCalcu();
}

/**
* 比较优先级
*
* @param next
* @param prev
* @return
*/
private boolean priority(String next, String prev) {
return (highOperator.contains(next)
&& lowOperator.contains(prev))
|| "(".equals(prev)
|| "(".equals(next);
}

/**
* 对两个数字进行计算
*
* @param front
* @param after
* @param sign
* @return
*/
private int calcIntegers(int front, int after, String sign) {
switch (sign) {
case "+":
return front + after;
case "-":
return front - after;
case "*":
return front * after;
case "/":
return front / after;
default:
throw new RuntimeException("Sign Invalid! sign=" + sign);
}
}

public static void main(String[] args) {
long startTime = System.currentTimeMillis();
MyBasicCalculator solution = new MyBasicCalculator();
System.out.println(solution.calculate("1 + 1 - 3 + 4 - (8 + 2) - 4 + 3 - 1 - 4 + 6 - 9 + 1"));
System.out.println(solution.calculate("(1+(4+5+2)-3)+(6+8)"));
System.out.println(solution.calculate("1-(5)"));
System.out.println(solution.calculate("2-4-(8+2-6+(8+4-(1)+8-10))"));
System.out.println(System.currentTimeMillis() - startTime);
}
}

源码

巧妙的解法

下面我们来看看网上比较好的解法,相比于我的代码,简直不要爽太多,膜拜…… LeetCode上运行只需要耗时 27 ms.

思路

  1. 解析多位整数。比如解析123,第一次循环为 1 * 10 + 2 = 12,第二次循环为 12 * 10 + 3 = 123
  2. 处理加减号。不是存储入到操作符栈,而是转为正负号,待到下一次循环时,与前面的累计结果进行相加;
  3. 处理括号。如果遇到 左括号 (,就将前面累计的结果与正负存储操作数栈,并将累计结果清空,正负号标记为正。等到遇到右括号 )时,就将这一次累计的结果与操作数栈顶存储的累计结果进行累加,得到一个最终结果;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
package one.wangwei.leetcode.stack;

import java.util.Stack;

/**
* 简单计算器实现
*
* @author https://wangwei.one
* @date 2019/1/18
*/
public class BasicCalculator {

/**
* 运算表达式
*
* @param s
* @return
*/
public int calculate(String s) {
// 操作数栈
Stack<Integer> stack = new Stack<>();
// 正负号
int sign = 1;
// 累计结果
int result = 0;
for (int i = 0; i < s.length(); i++) {
if (Character.isDigit(s.charAt(i))) {
// 字符转换
int num = s.charAt(i) - '0';
// 处理多位整数
while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
num = num * 10 + s.charAt(i + 1) - '0';
i++;
}
result += num * sign;
} else if (s.charAt(i) == '+') {
sign = 1;
} else if (s.charAt(i) == '-') {
sign = -1;
} else if (s.charAt(i) == '(') {
stack.push(result);
stack.push(sign);
result = 0;
sign = 1;
} else if (s.charAt(i) == ')') {
result = result * stack.pop() + stack.pop();
}
}
return result;
}

public static void main(String[] args) {
BasicCalculator calculator = new BasicCalculator();
System.out.println(calculator.calculate("2-4-(8+2-6 + (8 +4 -(1)+8-10))"));
}

}

源码

知道原理是一回事,自己动手去实现,又是另外一回事!

参考资料

请我喝半杯☕️