题目：

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.

链接： 

题解：

比较简练的方法就是把String根据运算符先split一下，之后再计算各部分，另外也可以用Token来做。自己做的方法比较繁琐，就是从头到尾遍历String，然后根据运算符的不同做一些特殊的处理。这里几个小地方，比如一开始 s += '+'来处理最后的元素，保存之前的运算符，之前运算的结果等等。二刷的时候一定要好好优化。

Time Complexity - O(n)， Space Complexity - O(1)

public class Solution {    public int calculate(String s) {        if(s == null || s.length() == 0)            return 0;        s += '+';            char prevOperator = '+';        int res = 0, prevNum = 0, curNum = 0;                for(int i = 0; i < s.length(); i++) {            char c = s.charAt(i);            if(c == ' ')                continue;            else if (Character.isDigit(c))                curNum = curNum * 10 + (int)(c - '0');            else if (c == '+' || c == '-') {                if(prevOperator == '+' || prevOperator == '-') {                    if(prevOperator == '+') {                        res += prevNum + curNum;                    } else {                        res += prevNum - curNum;                    }                } else {                    if(prevOperator == '*')                        res += prevNum * curNum;                    else                        res += prevNum / curNum;                }                curNum = 0;                prevNum = 0;                prevOperator = c;            } else if (c == '*' || c == '/') {                if(prevOperator == '+')                    prevNum = curNum;                else if(prevOperator == '-')                    prevNum = -curNum;                  else if(prevOperator == '*')                    prevNum *= curNum;                else if(prevOperator == '/')                    prevNum /= curNum;                                    curNum = 0;                prevOperator = c;            }        }                            return res;    }}

 

Reference:

https://leetcode.com/discuss/41790/10-16-lines-java-easy

https://leetcode.com/discuss/41558/20ms-o-n-time-o-1-space-one-scan-c-solution

https://leetcode.com/discuss/41641/17-lines-c-easy-20-ms

https://leetcode.com/discuss/41902/share-my-java-solution

https://leetcode.com/discuss/42903/java-straight-forward-iteration-solution-with-comments-stack

https://leetcode.com/discuss/42423/28ms-code-with-stacks-for-oprand-extension-cover-also-given