【数据结构与算法】使用栈Stack来实现后缀表达式(逆波兰表达式)求值

1. 前缀表达式的介绍

前缀表达式也叫波兰表达式。前缀表达式的运算符位于数字之前，例如(3+4)*5-6 对应的前缀表达式就是- * + 3 4 5 6。因为前缀表达式使用的不多，这里我们只要了解即可，不用关系中缀表达式如何转换成前缀表达式

通过前缀表达式求值的步骤：

从右至左遍历表达式，遇到数字时，将数字压入栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈；重复上述过程直到遍历完成，最后运算得出的值即为表达式的结果

例如: (3+4)*5-6对应的前缀表达式就是- * + 3 4 5 6 , 针对前缀表达式求值步骤如下:

1. 从右至左遍历表达式，将6、5、4、3压入栈
2. 遇到+运算符，因此弹出3和4，计算出3+4的值，得7，再将7入栈
3. 接下来是运算符，因此弹出7和5，计算出75=35，将35入栈
4. 最后是-运算符，计算出35-6的值，即29，由此得出表达式最终结果

2. 中缀表达式的介绍

中缀表达式就是常见的运算表达式，如(3+4)*5-6。但对计算机来说却不好操作，有时计算的结果不正确。因此在计算结果时，往往会将中缀表达式转成后缀表达式来操作

3. 后缀表达式的介绍

后缀表达式也叫逆波兰表达式。与前缀表达式相似，只是运算符位于数字之后。例如(3+4)*5-6对应的后缀表达式就是3 4 + 5 * 6 –

4. 将中缀表达式转换成后缀表达式

后缀表达式适合计算机进行运算，但是对人却不友好，我们需要将中缀表达式转成后缀表达式

转换步骤如下：

1. 初始化一个栈stack用来储存运算符，和一个集合list用来储存中间结果
2. 从左至右遍历中缀表达式
3. 遇到数字时，将添加到list；
4. 遇到括号时：
   1. 如果是左括号“(”，则直接压入stack
   2. 如果是右括号“)”，则依次弹出stack栈顶的运算符，并添加到list，直到遇到左括号为止，并将左括号弹出并丢弃
5. 遇到运算符时，比较其与stack栈顶运算符的优先级：
   1. 如果stack不为空，且栈顶运算符不为左括号"("，且小于等于栈顶运算符的优先级，则将栈顶运算符弹出并添加到list中。再次循环处理5-1
   2. 否则直接将运算符入栈
6. 重复步骤2至5，直到遍历表达式完成
7. 将stack中剩余的运算符依次弹出并添加到list
8. 遍历list的值，即为后缀表达式

中缀表达式(3+4)*5-6，转换成后缀表达式的结果为3 4 + 5 * 6 -

5. 通过后缀表达式进行求值

通过后缀表达式求值的步骤：

从左至右遍历表达式，遇到数字时，将数字压入栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈；重复上述过程直到遍历完成，最后运算得出的值即为表达式的结果

例如: (3+4)*5-6对应的后缀表达式就是3 4 + 5 * 6 -, 针对后缀表达式求值步骤如下:

1. 从左至右遍历，将3和4压入栈
2. 遇到+运算符，因此弹出4和3，计算出3+4的值，得7，再将7入栈
3. 将5入栈
4. 接下来是运算符，因此弹出5和7，计算出75=35，将35入栈
5. 将6入栈
6. 最后是-运算符，计算出35-6的值，即29，由此得出表达式最终结果

6. 逆波兰表达式的代码实现

需求：输入一个中缀表达式，支持小括号和多位数正数，运算符支持+、-、*、/四种。先使用栈Stack转换成逆波兰表达式，最后使用栈Stack对逆波兰表达式进行计算，得出表达式结果 输入一个逆波兰表达式(后缀表达式)，使用栈(Stack), 计算其结果

实现如下：

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

public class ReversePolishNotation {

    public static void main(String[] args) {
        
        String infixExpression = "(3+4)*5-6";

        // 中缀表达式转成列表
        List infixList = infixExpression2List(infixExpression);
        System.out.println(infixList);

        // 中缀列表，转换成后缀列表
        List suffixList = infixList2SuffixList(infixList);
        System.out.println(suffixList);

        int result = reversePolishCalculate(suffixList);
        System.out.printf("表达式：%s的计算结果为：%d\n", infixExpression, result);
    }


    // 将中缀表达式转换成list
    public static List infixExpression2List(String infixExpression) {
        List infixList = new ArrayList();
        int index = 0;
        char tmpChar;
        String concatNumber = ""; // 用于拼接多位数字字符

        while (index < infixExpression.length()) {
            tmpChar = infixExpression.charAt(index);

            // 如果是一个非数字，则直接添加到list，然后进行下一轮遍历
            if (tmpChar < 48 || tmpChar > 57) {
                infixList.add("" + tmpChar);
            } else {
                // 如果是一个数字，则拼接到数字字符串
                concatNumber += tmpChar;

                // 如果当前字符是最后一个字符，或当前字符的下一个字符是非数字
                // 则将数字字符串添加到list, 然后将数字字符串变为""
                if (index == (infixExpression.length() - 1) ||
                        infixExpression.charAt(index + 1) < 48 ||
                        infixExpression.charAt(index + 1) > 57) {
                    infixList.add(concatNumber);
                    concatNumber = "";
                }
            }

            index++;
        }

        return infixList;
    }


    // 将中缀表达式列表，转换成后缀表达式列表
    public static List infixList2SuffixList(List infixList) {
        // stack用来储存运算符
        Stack stack = new Stack();
        // suffixList用来储存中间结果
        List suffixList = new ArrayList();

        for (String infix : infixList) {
            // 如果是一个数，添加到suffixList
            if (infix.matches("\\d+")) {
                suffixList.add(infix);
            } else if (infix.equals("(")) {
                // 如果是左括号“(”，则直接压入stack
                stack.push(infix);
            } else if (infix.equals(")")) {
                // 如果是右括号“)”，则依次弹出stack栈顶的运算符，并添加到suffixList，直到遇到左括号为止，并将左括号弹出并丢弃
                while (!stack.peek().equals("(")) {
                    suffixList.add(stack.pop());
                }
                stack.pop();
            } else {
                // 运算符处理

                // 如果stack不为空，且栈顶运算符不为左括号"("，且小于等于栈顶运算符的优先级，则将栈顶运算符弹出并添加到suffixList中。再次循环处理5-1
                // 否则直接将运算符入栈
                while (!stack.isEmpty() && stack.peek() != "(" && getOperationPriority(infix)