# 0227. Basic Calculator II

https://leetcode.com/problems/basic-calculator-ii

## Description

Given a string `s` which represents an expression, _evaluate this expression and return its value_.&#x20;

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of `[-231, 231 - 1]`.

**Note:** You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as `eval()`.

**Example 1:**

```
**Input:** s = "3+2*2"
**Output:** 7
```

**Example 2:**

```
**Input:** s = " 3/2 "
**Output:** 1
```

**Example 3:**

```
**Input:** s = " 3+5 / 2 "
**Output:** 5
```

**Constraints:**

* `1 <= s.length <= 3 * 105`
* `s` consists of integers and operators `('+', '-', '*', '/')` separated by some number of spaces.
* `s` represents **a valid expression**.
* All the integers in the expression are non-negative integers in the range `[0, 231 - 1]`.
* The answer is **guaranteed** to fit in a **32-bit integer**.

## ac1

intuitive solution, so disgusting.

```java
class Solution {
    public int calculate(String s) {
        Queue<String> queue = new LinkedList<String>();
        Deque<String> deque = new ArrayDeque<String>();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ' ') continue;
            if (c != '+' && c != '-' && c != '*' && c != '/') {
                sb.append(c);
            } else {
                queue.offer(sb.toString());
                queue.offer(String.valueOf(c));
                sb.setLength(0);
            }
        }
        queue.offer(sb.toString());

        while (!queue.isEmpty()) {
            String c = queue.poll();
            if (c.equals("*") || c.equals("/")) {
                String operand = queue.poll();
                String num = deque.pollLast();
                switch (c) {
                    case "*":
                        int tmp = Integer.parseInt(num) * Integer.parseInt(operand);
                        deque.offer("" + tmp);
                        break;
                    case "/":
                        tmp = Integer.parseInt(num) / Integer.parseInt(operand);
                        deque.offer("" + tmp);
                }
            } else {
                deque.offer(c);
            }
        }

        int val = Integer.parseInt(deque.poll());
        while (!deque.isEmpty()) {
            String operator = deque.poll();
            String operand = deque.poll();
            switch(operator) {
                case "+":
                    val += Integer.parseInt(operand);
                    break;
                case "-":
                    val -= Integer.parseInt(operand);
            }
        }

        return val;
    }
}
```

## ac2:

```java
class Solution {
    public int calculate(String s) {
        Stack<Integer> nums = new Stack<>();
        nums.push(1);
        Character oper = '*';
        int n = 0;

        s.replace(" ", "");
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // if (c == ' ') continue;
            if (Character.isDigit(c)) {
                n = n * 10 + c - '0';
            }
            // can't else if, because need to handle last number of expression
            if (i == s.length() - 1 || c == '+' || c == '-' || c == '*' || c == '/') {
                switch (oper) {
                    case '+': nums.push(n);break;
                    case '-': nums.push(-n);break;
                    case '*': nums.push(nums.pop() * n);break;
                    case '/': nums.push(nums.pop() / n);break;
                }
                n = 0;
                oper = c;
            }
        }

        // add values in stack
        int res = 0;
        for (int i : nums) res += i;

        return res;
    }
}
/*
The essential idea is the same as 2 stack #772, keep track of numbers and operators. This one is simplified, one variable to record operator is fire enough.
*/
```
