题目
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
示例 2：
示例 3：
1
2
| 输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23
|
提示：
- 1 <= s.length <= 3 * 105
- s 由数字、’+’、’-‘、’(‘、’)’、和 ‘ ‘ 组成
- s 表示一个有效的表达式
- ‘+’ 不能用作一元运算(例如， “+1” 和 “+(2 + 3)” 无效)
- ‘-‘ 可以用作一元运算(即 “-1” 和 “-(2 + 3)” 是有效的)
- 输入中不存在两个连续的操作符
- 每个数字和运行的计算将适合于一个有符号的 32位 整数
解答
因为以前大学的时候曾经学习过使用两个栈做表达式运算，所以看完题目后，便顺着这个思路解题
代码如下
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
| class Solution {
public int calculate(String s) {
LinkedList<Integer> data = new LinkedList<>();
LinkedList<Character> operator = new LinkedList<>();
s = s.replace(" ", "");
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
switch (c){
case '(':
if( (i+1) < s.length() && s.charAt(i+1) == '-' ){
data.push(0);
}
operator.push(c);
break;
case '+':
case '-':
operator.push(c);
break;
case ')':
operator.pop();
int popNum = data.pop();
calculateNum(popNum, data, operator);
break;
default:
StringBuilder sb = new StringBuilder();
sb.append(c);
int j = 1;
while ( (i+j) < s.length() && Character.isDigit(s.charAt(i+j)) ){
sb.append(s.charAt(i+j));
j++;
}
i = i+j-1;
int currentNum = Integer.parseInt(sb.toString());
calculateNum(currentNum, data, operator);
}
}
return data.pop();
}
public static void calculateNum(int currentNum, LinkedList<Integer> data, LinkedList<Character> operator) {
if( operator.size() == 0 ){
data.push(currentNum);
return;
}
boolean hasUseCurrentNum = false;
while (operator.size() > 0){
if('+' == operator.peek()){
operator.pop();
int temp = data.pop();
data.push(temp+currentNum);
hasUseCurrentNum = true;
} else if ('-' == operator.peek()){
operator.pop();
int temp = 0;
if(data.size() > 0){
temp = data.pop();
}
data.push(temp-currentNum);
hasUseCurrentNum = true;
} else {
if(!hasUseCurrentNum){
data.push(currentNum);
}
break;
}
}
}
}
|
Java里面的栈Stack底层是数组结构，在容量不够时，难免会涉及扩容，扩容则需要迁移数据，效率较低。这里使用LinkedList作为栈使用。下图第二行是使用Stack实现，执行用时56ms，第一行是使用LinkedList实现，执行用时17ms
题目转载自：https://leetcode-cn.com/problems/basic-calculator
