leetcode [227]Basic Calculator II
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
Example 1:
Input: "3+2*2" Output: 7
Example 2:
Input: " 3/2 " Output: 1
Example 3:
Input: " 3+5 / 2 " Output: 5
Note:
- You may assume that the given expression is always valid.
- Do not use the
evalbuilt-in library function.
题目大意：
计算表达式最后的结果值，表达式可能含有+，-，×，/, 空格和数字，并且最后结果一定是整型。
解法：
因为乘法和除法是优先于加法和减法的计算，所以将乘法和除法都计算出来，使得表达式里面只有加法和减法，并使用两个List，一个存储数字，一个存储加减符号。
java:
class Solution {
public int calculate(String s) {
List<Integer>nums=new LinkedList<>();
List<Character>ops=new LinkedList<>();
int index=0;
int res=0;
while(index<s.length()){
if (s.charAt(index)==' '){
index++;
continue;
}
else if (s.charAt(index)=='+'||s.charAt(index)=='-') {
ops.add(s.charAt(index));
index++;
}
else if(s.charAt(index)=='*'){
index++;
int a=((LinkedList<Integer>) nums).getLast();
nums.remove(nums.size()-1);
StringBuilder str=new StringBuilder();
while (index<s.length()&&((s.charAt(index)>='0' && s.charAt(index)<='9')||s.charAt(index)==' ')){
if(s.charAt(index)!=' ') str.append(s.charAt(index));
index++;
}
int b=Integer.parseInt(str.toString());
nums.add(a*b);
}else if(s.charAt(index)=='/'){
index++;
int a=((LinkedList<Integer>) nums).getLast();
nums.remove(nums.size()-1);
StringBuilder str=new StringBuilder();
while (index<s.length()&&((s.charAt(index)>='0' && s.charAt(index)<='9')||s.charAt(index)==' ')){
if(s.charAt(index)!=' ') str.append(s.charAt(index));
index++;
}
int b=Integer.parseInt(str.toString());
nums.add(a/b);
}
else if (s.charAt(index)>='0' && s.charAt(index)<='9'){
StringBuilder str=new StringBuilder();
while (index<s.length()&&s.charAt(index)>='0' && s.charAt(index)<='9'){
if(s.charAt(index)!=' ') str.append(s.charAt(index));
index++;
}
nums.add(Integer.parseInt(str.toString()));
}
}
while (!ops.isEmpty()){
char c=((LinkedList<Character>) ops).getFirst();
ops.remove(0);
int num1=((LinkedList<Integer>) nums).getFirst();
nums.remove(0);
int num2=((LinkedList<Integer>) nums).getFirst();
nums.remove(0);
if(c=='+'){
res=num1+num2;
}if(c=='-') {
res=num1-num2;
}
nums.add(0,res);
}
return nums.isEmpty()?0:((LinkedList<Integer>) nums).getFirst();
}
}
我的做法太复杂了，应该将表达式中的加减乘除最后都只转换成加号，最后将加法所需的数字存储在一个栈中，将这个栈中的数字相加就可以了。
class Solution {
public int calculate(String s) {
int len=0;
if(s==null||s.length()==0) return 0;
len=s.length();
int num=0;
char sign='+';
Stack<Integer>stack=new Stack<>();
for(int i=0;i<len;i++){
if(Character.isDigit(s.charAt(i))){
num=num*10+s.charAt(i)-'0';
}
if((!Character.isDigit(s.charAt(i))&&s.charAt(i)!=' ')||i==len-1){
if (sign=='+') stack.push(num);
else if (sign=='-') stack.push(-num);
else if (sign=='*') stack.push(stack.pop()*num);
else{
stack.push(stack.pop()/num);
}
sign=s.charAt(i);
num=0;
}
}
int res=0;
for(int i:stack){
res+=i;
}
return res;
}
}
更多精彩
