栈

后进先出

1. 顺序栈

1. 定义栈顶top，初始值为-1
2. 入栈：stack[++top] = data
3. 出栈：return stack[top--]
4. 栈空：top == -1
5. 栈满：top == capacity - 1

public class MyStack<E> {
    // 栈的最大容量
    private int capacity;
    // 采用数组实现栈
    private E[] stack;
    // 栈顶索引
    private int top = -1;

    public MyStack(int capacity) {
        this.capacity = capacity;
        stack = (E[]) new Object[capacity];
    }

    public boolean empty() {
        return top == -1;
    }

    public boolean full() {
        return top == capacity - 1;
    }

    public int size() {
        return top + 1;
    }

    public E push(E item) {
        if (full()) {
            throw new RuntimeException("full");
        }
        // 先将top++，在赋值
        stack[++top] = item;
        return item;
    }

    public E pop() {
        if (empty()) {
            throw new RuntimeException("empty");
        }
        // 先获取栈顶值，再将top--
        return stack[top--];
    }

    public E peek() {
        if (empty()) {
            throw new RuntimeException("empty");
        }
        return stack[top];
    }
}

2. 中缀表达式

利用栈计算中缀表达式结果思路：

1. 从左至右遍历中缀表达式，依次取出表达式的每一个字符
2. 若取出的字符是运算符：
   1. 如果符号栈为空，直接入符号栈
   2. 如果符号栈不为空，判断当前操作符与栈顶操作符的优先级
      1. 当前操作符优先级小于或等于栈顶操作符：计算，然后将当前操作符压入符号栈
      2. 当前操作符优先级大于栈中的操作符，直接入符号栈
3. 若取出的字符是操作数：分析出完整的运算数
   1. 如果当前已经是最后一位，则入栈
   2. 如果下一个字符是符号，则入栈
4. 计算，直到符号栈为空
5. 最后数字栈中仅剩的数字就是表达式结果

• 计算过程：
  1. 从数字栈pop出两个数
  2. 从符号栈顶pop出一个符号
  3. 计算，将运算结果压入数字栈

中缀表达式代码实现：

import java.util.Stack;

public class Calculator {
    // 获取符号优先级
    public static int priority(char operation) {
        if (operation == '*' || operation == '/')
            return 1;
        else if (operation == '+' || operation == '-')
            return 0;
        else
            return -1;
    }

    // 判断字符是否为符号
    public static boolean isOperation(char value) {
        return value == '+' || value == '-' || value == '*' || value == '/';
    }

    // 计算 left operation right
    public static int calc(int left, int right, int operation) {
        int result = 0;
        switch (operation) {
            case '+':
                result = left + right;
                break;
            case '-':
                result = left - right;
                break;
            case '*':
                result = left * right;
                break;
            case '/':
                result = left / right;
                break;
        }
        return result;
    }

    public static void main(String[] args) {
        String expression = "320+200*5-12/2";
        // 数字栈
        Stack<Integer> numStack = new Stack<>();
        // 符号栈
        Stack<Character> opeStack = new Stack<>();
        int left, right, result;
        char ch = ' ', operation;
        String curNum = "";
        // 从左至右遍历中缀表达式，依次取出表达式的每一个字符
        for (int i = 0; i < expression.length(); i++) {
            ch = expression.charAt(i);
            // 若取出的字符是运算符
            if (isOperation(ch)) {
                // 如果符号栈为空，直接入符号栈
                if (opeStack.empty()) {
                    opeStack.push(ch);
                } else {
                    // 如果符号栈不为空，判断当前操作符与栈顶操作符的优先级
                    // 当前操作符优先级小于或等于栈顶操作符
                    if (priority(ch) <= priority(opeStack.peek())) {
                        // 从数字栈pop出两个数
                        right = numStack.pop();
                        left = numStack.pop();
                        // 从符号栈顶pop出一个符号
                        operation = opeStack.pop();
                        // 进行运算
                        result = calc(left, right, operation);
                        // 将运算结果压入数字栈
                        numStack.push(result);
                        // 将当前操作符压入符号栈
                        opeStack.push(ch);
                    } else {
                        // 当前操作符优先级大于栈中的操作符，直接入符号栈
                        opeStack.push(ch);
                    }
                }
            } else {
                // 若取出的字符是操作数：分析出完整的运算数
                curNum += ch;
                // 如果当前已经是最后一位，则入栈
                if (i == expression.length() - 1) {
                    numStack.push(Integer.parseInt(curNum));
                    curNum = "";
                } else if (isOperation(expression.charAt(i + 1))) {
                    // 如果下一个字符是符号，则入栈
                    numStack.push(Integer.parseInt(curNum));
                    // 清空curNum
                    curNum = "";
                }
            }
        }

        // 从数字栈取出两个数，从符号栈取出一个符号，计算，直到符号栈为空
        while (!opeStack.empty()) {
            right = numStack.pop();
            left = numStack.pop();
            operation = opeStack.pop();
            result = calc(left, right, operation);
            numStack.push(result);
        }
        // 最后数字栈中仅剩的数字就是表达式结果
        // 320+200*5-12/2=1314
        System.out.println(expression + "=" + numStack.pop());
    }
}

3. 中缀转后缀

中缀表达式转换为逆波兰表达式的思路：

1. 初始化两个栈：运算符栈o和结果栈r
2. 从左至右遍历中缀表达式，依次取出表达式的每一个字符
3. 若取出的字符是操作数，则将该操作数压入r栈
4. 若取出的字符是左括号'('，直接压入o
5. 若取出的字符是右括号')'，则依次弹出o栈顶运算符，并压入r，直到遇到左括号为止，此时将这一对括号丢弃
6. 若取出的字符是运算符：
   1. 若o为空或栈顶运算符为左括号'('，则直接将运算符压入o
   2. 若当前运算符优先级比栈顶运算符高，则直接将运算符压入o
   3. 若当前运算符优先级比栈顶运算符低，将o栈中优先级比当前运算符优先级高的运算符压入到r栈中，再将当前运算符压入o栈
7. 将o中剩余的运算符依次弹出并压入r
8. 依次弹出r中元素并输出，结果的逆序即中缀表达式对应的后缀表达式

后缀表达式计算器代码实现：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

// 逆波兰表达式计算器
public class ReversePolishCalculator {
    public static void main(String[] args) {
        String expression = "(3*(300+100)+200)/2+614";
        List<String> infixExpressionList = toInfixExpressionList(expression);
        List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
        // 中缀表达式：[(, 3, *, (, 300, +, 100, ), +, 200, ), /, 2, +, 614]
        System.out.println("中缀表达式：" + infixExpressionList);
        // 后缀表达式：[3, 300, 100, +, *, 200, +, 2, /, 614, +]
        System.out.println("后缀表达式：" + suffixExpressionList);
        // 计算结果：1314
        System.out.println("计算结果：" + calc(suffixExpressionList));
    }

    // 1. 将中缀表达式转为对应的List
    public static List<String> toInfixExpressionList(String s) {
        List<String> list = new ArrayList<>();
        // 用于遍历中缀表达式
        int i = 0;
        // 用于拼接数字
        String num;
        // 存放遍历到的字符
        char c;
        do {
            c = s.charAt(i);
            // 如果c不是数字，加入到list中
            if (c < '0' || c > '9') {
                list.add("" + c);
                i++;
            } else {
                // 如果是一个数字，需要考虑多位数
                num = "";
                while (i < s.length() && '0' <= (c = s.charAt(i)) && c <= '9') {
                    num += c;
                    i++;
                }
                list.add(num);
            }
        } while (i < s.length());
        return list;
    }

    // 2. 将中缀表达式对应的List转换为后缀表达式对应的List
    public static List<String> parseSuffixExpressionList(List<String> list) {
        Stack<String> oStack = new Stack<>(); // 符号栈
        // r栈在转换过程中没有pop操作
        Stack<String> rStack = new Stack<>();
        // 从左至右遍历中缀表达式，依次取出表达式的每一个字符
        for (String item : list) {
            if (item.matches("\\d+")) {
                // 若取出的字符是操作数，则将该操作数压入r栈
                rStack.push(item);
            } else if (item.equals("(")) {
                // 若取出的字符是左括号'('，直接压入o
                oStack.push(item);
            } else if (item.equals(")")) {
                // 若取出的字符是右括号')'，则依次弹出o栈顶运算符，并压入r，直到遇到左括号为止，此时将这一对括号丢弃
                while (!oStack.peek().equals("(")) {
                    rStack.push(oStack.pop());
                }
                // )未在栈中，不用丢弃；丢弃(
                oStack.pop();
            } else {
                // 若优先级比栈顶运算符低：
                // 将o栈中优先级比当前运算符优先级高的，压入到r栈中
                while (oStack.size() != 0 && priority(item) < priority(oStack.peek())) {
                    rStack.push(oStack.pop());
                }

                // 若o为空，则不会执行上面的循环
                // 若栈顶运算符为左括号'('，则priority(oStack.peek()为-1，不会执行上面的循环
                // 若当前运算符优先级比栈顶运算符高，则不会执行上面的循环
                // 将当前运算符压入o栈
                oStack.push(item);
            }
        }
        // 将o中剩余的运算符依次弹出并压入r
        while (oStack.size() != 0) {
            rStack.push(oStack.pop());
        }
        return rStack;
    }

    // 3. 对逆波兰表达式的计算
    public static int calc(List<String> list) {
        Stack<String> stack = new Stack<>();
        int result = 0;
        for (String item : list) {
            // 如果是数字：入栈
            if (item.matches("\\d+")) {
                stack.push(item);
            } else {
                // 是运算符：pop出两个数，计算，然后入栈
                int right = Integer.parseInt(stack.pop());
                int left = Integer.parseInt(stack.pop());
                if (item.equals("+"))
                    result = left + right;
                else if (item.equals("-"))
                    result = left - right;
                else if (item.equals("*"))
                    result = left * right;
                else if (item.equals("/"))
                    result = left / right;
                else {
                    throw new RuntimeException("运算符有误");
                }
                // 将result入栈
                stack.push("" + result);
            }
        }
        // 最后留在栈里的就是结果
        return Integer.parseInt(stack.pop());
    }

    // 获取符号优先级
    public static int priority(String operation) {
        if ("*".equals(operation) || "/".equals(operation))
            return 1;
        else if ("+".equals(operation) || "-".equals(operation))
            return 0;
        else
            return -1;
    }
}