-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBasicCalculator_225.java
More file actions
128 lines (118 loc) · 4.17 KB
/
Copy pathBasicCalculator_225.java
File metadata and controls
128 lines (118 loc) · 4.17 KB
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
package Stack_Queue;
import java.util.Deque;
import java.util.LinkedList;
/**
* 实现基本的计算器
* + - * / 没有括号
*/
public class BasicCalculator_225 {
/**
* 先计算乘除，再计算加减
* 将乘除计算出来的结果，放回原先位置，最后计算一系列值的加法
* 比如 2+3*4 ---> +2+3*4
* 遍历字符串 s，并用变量 preSign记录每个数字之前的运算符，
* 对于第一个数字，其之前的运算符视为加号。每次遍历到数字末尾时，根据 preSign来决定计算方式：
* 加号：入栈
* 减号：相反数入栈
* 乘除：计算数字与栈顶元素，并将栈顶元素替换为计算结果
*
*/
public static int calculateFast(String s){
if(s==null||s.length()==0) return 0;
char preSign='+';
int num=0;
int len=s.length();
Deque<Integer> stack=new LinkedList<>();
for(int i=0;i<len;i++){
if(Character.isDigit(s.charAt(i))){
num=10*num+(s.charAt(i)-'0');
}
if(!Character.isDigit(s.charAt(i))&&s.charAt(i)!=' '||i==len-1){
switch (preSign){
case '+': stack.push(num);break;
case '-': stack.push(-num);break;
case '*': stack.push(num*stack.pop());break;
default:
stack.push(stack.pop()/num);
}
preSign=s.charAt(i);
//复原
num=0;
}
}
int ans=0;
while (!stack.isEmpty()){
ans+=stack.pop();
}
return ans;
}
public static int calculate(String s) {
if(s==null||s.length()==0) return 0;
Deque<Long> dataStack=new LinkedList<>();
Deque<Character> opeStack=new LinkedList<>();
int i=0;
int len=s.length();
while (i<len){
if(' '==s.charAt(i)){
i++;
}else if('+'==s.charAt(i)||'-'==s.charAt(i)){
while(!opeStack.isEmpty()){
long num2=dataStack.pop();
long num1=dataStack.pop();
dataStack.push(cal(num1,opeStack.pop(),num2));
}
opeStack.push(s.charAt(i));
i++;
}else if('*'==s.charAt(i)){
if(!opeStack.isEmpty()&&(opeStack.peek()=='*'||opeStack.peek()=='/')){
long num2=dataStack.pop();
long num1=dataStack.pop();
dataStack.push(cal(num1,opeStack.pop(),num2));
}
opeStack.push(s.charAt(i));
i++;
}else if('/'==s.charAt(i)){
if(!opeStack.isEmpty()&&(opeStack.peek()=='*'||opeStack.peek()=='/')){
long num2=dataStack.pop();
long num1=dataStack.pop();
dataStack.push(cal(num1,opeStack.pop(),num2));
}
opeStack.push(s.charAt(i));
i++;
}else{
long tmp=0;
while(i<len&&Character.isDigit(s.charAt(i))){
tmp=10*tmp+(s.charAt(i)-'0');
i++;
}
dataStack.push(tmp);
}
}
while (!opeStack.isEmpty()){
long num2=dataStack.pop();
long num1=dataStack.pop();
dataStack.push(cal(num1,opeStack.pop(),num2));
}
return dataStack.pop().intValue();
}
private static long cal(long m,char sym,long n){
long ans=0;
switch (sym){
case '+': ans=m+n; break;
case '-': ans=m-n; break;
case '*': ans=m*n; break;
case '/': ans=m/n; break;
default:
break;
}
return ans;
}
public static void main(String[] args) {
int calculate = calculate("2*3*4");
System.out.println(calculate);
int calculate1 = calculate(" 3/2 ");
System.out.println(calculate1);
int calculate2 = calculate(" 3+5 / 2 ");
System.out.println(calculate2);
}
}