# Stack

## 应用场景

任何需要记住最近一步运算结果的场景。

## 使用技巧

掌握好两个操作，**入栈**与**出栈**。

1。入栈，通常是为了**保存**之前的运算结果，**即已经完成了运算的一些节点**。                                                        _For example_，_binary tree pre-order traversal，栈里存的就是已经遍历过当前节点和左子树的所有节点，出栈的时候只需要判断右子树即可。_

2。出栈，通常是为了进行**新的计算**。

{% hint style="info" %}
括号一类的题目用 Stack 来判断 开 与 闭，非常方便。
{% endhint %}

## 经典题目

[_150 Evaluate Reverse Polish Notation_](https://leetcode.com/problems/evaluate-reverse-polish-notation/description/)

栈的经典题之一。每次遇到操作符，从栈中pop 头两个数字；每次遇到数字，直接进栈。

```java
public int evalRPN(String[] tokens) {
    Deque<Integer> numbers = new LinkedList<>();
    for (String cur: tokens) {
        if (cur.equals("+")) {
            int first = numbers.pollLast();
            int second = numbers.pollLast();
            numbers.add(first + second);
        } else if (cur.equals("-")) {
            int first = numbers.pollLast();
            int second = numbers.pollLast();
            numbers.add(second - first);
        } else if (cur.equals("*")) {
            int first = numbers.pollLast();
            int second = numbers.pollLast();
            numbers.add(first * second);
        } else if (cur.equals("/")) {
            int first = numbers.pollLast();
            int second = numbers.pollLast();
            numbers.add(second / first);
        } else {
            numbers.add(Integer.valueOf(cur));
        }
    }
    return numbers.pollLast();
}
```



[_224 Basic Calculator_](https://leetcode.com/problems/basic-calculator/description/)

很明显，要用Stack做。这题的难点在于，运算有加减法，优先级的话得先计算括号里的数。\
这里用3个变量，res代表目前括号里的目前结果，number代表目前的数，sign代表上一个符号。

```java
public int calculate(String s) {
    Deque<Integer> numberStack = new LinkedList<>();
    int res = 0;
    int number = 0;
    int sign = 1;
    for (int i = 0; i < s.length(); i++) {
        char cur = s.charAt(i);
        if (Character.isDigit(cur)) {
            number = number * 10 + (cur - '0');
        } else if (cur == '+') {
            res += sign * number;
            number = 0;
            sign = 1;
        } else if (cur == '-') {
            res += sign * number;
            number = 0;
            sign = -1;
        } else if (cur == '(') {
            numberStack.push(res);
            numberStack.push(sign);
            res = 0;
            sign = 1;
        } else if (cur == ')') {
            res += sign * number;
            number = 0;
            res *= numberStack.pop();
            res += numberStack.pop();
        }
    }
    if (number != 0) res += sign * number;
    return res;
}
```



[_227 Basic Calculator II_](https://leetcode.com/problems/basic-calculator-ii/description/)

```java
public int calculate(String s) {
    int number = 0;
    char sign = '+';
    Deque<Integer> numberStack = new LinkedList<>();
    
    for (int i = 0; i < s.length(); i++) {
        char cur = s.charAt(i);
        if (Character.isDigit(cur)) {
            number = number * 10 + (cur - '0');
        } 
        if ((!Character.isDigit(cur) && cur != ' ') || i == s.length() - 1) {
            if (sign == '+') {
                numberStack.push(number);
            } else if (sign == '-') {
                numberStack.push(-number);
            } else if (sign == '*') {
                numberStack.push(numberStack.pop() * number);
            } else if (sign == '/') {
                numberStack.push(numberStack.pop() / number);
            }
            number = 0;
            sign = cur;
        }
    }
    int res = 0;
    for (int i : numberStack) {
        res += i;
    }
    return res;
}
```
