1.题目描述：
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。
题目链接：https://leetcode-cn.com/problems/basic-calculator-ii/
2.解题思路及代码：
只要把中缀表达式转换为后缀表达式就可以用栈来计算表达式了。
中缀转后缀的方法：
- 数字直接输出到后缀表达式
- 栈为空时，遇到运算符，直接入栈
- 遇到运算符，弹出所有优先级大于或等于该运算符的栈顶元素，并将该运算符入栈
- 将栈中元素依次出栈
代码如下：
class Solution {
public int calculate(String s) {
return evalRPN(backEXP(s));
}
public ArrayList<String> backEXP(String s){
Stack<String> stk=new Stack<String>();
ArrayList<String> backExp=new ArrayList<String>();
for(int i=0;i<s.length();i++) {
if(Character.isDigit(s.charAt(i))) {
// 注意多位数的获取
int k = i + 1;
for (; k < s.length() && Character.isDigit(s.charAt(k)); k++) {
}
backExp.add(s.substring(i, k));
i = k - 1;
continue;
}else if(s.charAt(i)=='*'||s.charAt(i)=='/') {
while((!stk.empty())&&(stk.peek().equals("*")||stk.peek().equals("/"))) {
backExp.add(stk.pop());
}
stk.push(String.valueOf(s.charAt(i)));
}else if(s.charAt(i)=='+'||s.charAt(i)=='-') {
while(!stk.empty()){
backExp.add(stk.pop());
}
stk.push(String.valueOf(s.charAt(i)));
}
}
while(!stk.isEmpty()) {
backExp.add(stk.pop());
}
return backExp;
}
public int evalRPN(ArrayList<String> tokens) {
Stack<Integer> s=new Stack<Integer>();
for(String x:tokens) {
if(x.equals("+"))
s.push(s.pop()+s.pop());
else if(x.equals("-"))
s.push(-s.pop()+s.pop());
else if(x.equals("*"))
s.push(s.pop()*s.pop());
else if(x.equals("/")) {
int tmp=s.pop();
s.push(s.pop()/tmp);
}else
s.push(Integer.valueOf(x));
}
return s.pop();
}
}