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(); } }