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.
给出字符串,然后算出结果,我自己的思路是用Stack来做,如果遇见乘法和除法这种优先级高的算法,那么弹出stack元素,并取得队列的下一个元素,并计算,最后Stack里面只剩下数字和+/-法则,循环计算就可以得到结果
public int calculate(String s) {
Set<String> nset = new HashSet<String>();
for(char i = '0'; i <= '9'; i++){
nset.add(i + "");
}
Set<String> symbol1 = new HashSet<String>();
symbol1.add("+");symbol1.add("-");
Set<String> symbol2 = new HashSet<String>();
symbol2.add("*");symbol2.add("/");
Stack<String> stack = new Stack<String>();
StringBuilder sb = new StringBuilder();
List<String> list = new ArrayList<String>();
for(int i = 0; i < s.length(); i++){
if(nset.contains(s.charAt(i) + "")) {
sb.append(s.charAt(i));
}else if(s.charAt(i) == ' '){
continue;
}else{
list.add(sb.toString());
list.add(s.charAt(i) + "");
sb = new StringBuilder();
}
}
if(!"".equals(sb.toString())){
list.add(sb.toString());
}
for(int i = 0; i < list.size(); i++){
if(symbol2.contains(list.get(i))){
int a = Integer.valueOf(stack.pop());
int b = Integer.valueOf(list.get(i + 1));
if(list.get(i).equals("*")){
stack.push(a * b + "");
}else{
stack.push(a / b + "");
}
i ++;
}else{
stack.push(list.get(i));
}
}
int result = 0;
for(int i = 0; i< stack.size(); i++){
String a = stack.elementAt(i);
if(symbol1.contains(a)){
int b = Integer.valueOf(stack.elementAt(i + 1));
if(a.equals("-")){
b = 0 - b;
}
result += b;
i++;
}else{
result += Integer.valueOf(a);
}
}
return result;
}
网友评论