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.
You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.
代码如下：（超时）
public class Solution {
public int calculate(String s) {
s=s.replace(" ","");
s=s.replace("+"," + ");s=s.replace("-"," - ");s=s.replace("*"," * ");s=s.replace("/"," / ");
String[] ss=s.split(" ");
List<Integer> list=new ArrayList<>();
List<String> lists=new ArrayList<>();
for(int i=0;i<ss.length;i++)
{
if(ss[i].equals("+"))
lists.add(ss[i]);
else if(ss[i].equals("-"))
lists.add(ss[i]);
else if(ss[i].equals("*"))
{
int a=list.get(list.size()-1);
list.remove(list.size()-1);
int b=Integer.valueOf(ss[i+1]);
i++;
list.add(a*b);
}
else if(ss[i].equals("/"))
{
int a=list.get(list.size()-1);
list.remove(list.size()-1);
int b=Integer.valueOf(ss[i+1]);
i++;
if(a!=0)
list.add(a/b);
else
list.add(0);
}
else
list.add(Integer.valueOf(ss[i]));
}
while(lists.size()>0)
{
int a=list.get(0);
list.remove(0);
int b=list.get(0);
String c=lists.get(0);
lists.remove(0);
if(c.equals("+"))
list.set(0,a+b);
else
list.set(0,a-b);
}
return list.get(0);
}
}