# 227 Basic Calculator II

## 227. Basic Calculator II

## 1. Question

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.

## 2. Implementation

思路：这题只用考虑运算符号中乘号和除号需要考虑运算的优先级，但没有括号，所以整体来说难度降低了。和Basic Calculator I类似，我们仍然利用stack，但这时stack保存的不是正负号，而是之前运算的结果。当我们遇到加号或者减号时，直接将num或者-num放在stack。当我们遇到乘号或者除号时，我们需要将stack存的一个元素pop出来，与num相乘或者相除，然后再将结果放回stack。最后将stack的结果全都相加，得到最后的解。注意，当遇到输入只有数字，比如“111”，这类情况，我们必须在要将num放在stack里，不然最后stack是空的。

```java
class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int num = 0, res = 0;
        char sign = '+';
        Stack<Integer> stack = new Stack<>();
        int len = s.length();

        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);

            if (Character.isDigit(c)) {
                num = 10 * num + c - '0';
            }
            //字符是运算符或者到达字符串结束处，需要计算最后一次结果 
            if (isOperator(c) || i == len - 1) {
                if (sign == '+') {
                    stack.push(num);
                }
                else if (sign == '-') {
                    stack.push(-num);
                }
                else if (sign == '*') {
                    stack.push(stack.pop() * num);
                }
                else if (sign == '/') {
                    stack.push(stack.pop() / num);
                }
                sign = c;
                num = 0;
            }
        }

        while (!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }

    public boolean isOperator(char c ) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }
}
```

## 3. Time & Space Complexity

时间和空间都是O(n)

## 4. Follow Up

如果输入里还包含'(', ')'该怎么办？

<http://www.lintcode.com/en/problem/expression-evaluation/>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/my-algorithm-summary/data-structure/stack/227-basic-calculator-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.