波兰表达式与逆波兰表达式

1. 何为前缀（波兰）、中缀、后缀（逆波兰）表达式

1.1 前缀表达式

前缀表达式是一种没有括号的算数表达式，其与中缀表达式不同的是，运算符写在前面，操作数写在后面。一般形式的(3+4)×5-6即为中缀表达式，该中缀表达式对应的前缀表达式（或称波兰表达式）为：-×+3456

1.1.1 中缀表达式转前缀表达式

• 建立一个符号栈，并从右至左遍历表达式；

• 若遍历到数，则直接输出；

• 若遍历到右括号')'，直接压入栈顶（括号优先级最高，入栈时不比较）

• 若遇到左括号'('，表明括号已结束，不断弹出栈顶运算符并输出，直至弹出右括号')'，但该右括号只弹出不输出（相当于抵消左右括号，将其之间的运算符弹出并输出）；

• 若遇到其他运算符：

  • 栈为空时，直接入栈；
  • 若栈顶元素为右括号')'，直接入栈；
  • 若栈顶为其他运算符，则比较其优先级：注意此处优先级比较与后缀表达式的不同
    • 若优先级大于等于栈顶，则直接入栈；
    • 若优先级小于栈顶，弹出栈顶并输出，然后不断与新的栈顶比较，直至优先级大于等于栈顶或栈空或栈顶为右括号')'，再将该运算符入栈；

• 表达式遍历完毕，弹出符号栈内剩余所有运算符并输出，再逆序输出结果字符串，即为前缀表达式。

1.1.2 前缀表达式计算机求值

从右至左扫描前缀表达式，遇到数字直接入栈，遇到运算符弹出栈中两个元素，用运算符对其进行相应的运算，并将结果再次入栈。重复上述步骤直至遍历完表达式，最终运算的结果即为表达式的结果。eg.上述例子1+((2+3)×4)-5对应的前缀表达式为：-+1×+2345，针对该表达式求值步骤为：

• 从右至左扫描，将5，4，3，2压入栈中；
• 遇到'+'，弹出2，3计算2+3，并将结果5再次压入栈中；
• 遇到'×'，弹出5，4计算5×4，将结果20压入栈中；
• 1入栈；
• 遇到'+'，弹出1，20计算1+20，将结果21压入栈中；
• 遇到'-'，弹出21，5计算21-5，结果16即为表达式的值。

1.2 中缀表达式

中缀表达式对人来说更为熟悉，但对于计算机而言不好操作，因此在计算结果时，一般将中缀表达式转化成其他表达式来操作求值（一般转为后缀表达式，即逆波兰表达式）。

1.3 后缀表达式

后缀表达式又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作符之后。eg.(3+4)×5-6对应的后缀表达式为：34+5×6-。

1.3.1 中缀表达式转后缀表达式

• 建立一个符号栈，并从左至右遍历表达式；
• 若遍历到数，则直接输出；
• 若遍历到左括号'('，直接压入栈顶（括号优先级最高，入栈时不比较）；
• 若遇到右括号')'，则说明括号已结束，不断弹出栈顶运算符并输出，直至弹出左括号'('，但该左括号只弹出不输出（相当于抵消左右括号，将其之间的运算符弹出并输出）；
• 若遇到其他运算符：
  • 栈为空时，直接入栈；
  • 若栈顶元素为左括号'('，直接入栈；
  • 若栈顶为其他运算符，则比较其优先级：注意此处优先级比较与前缀表达式的不同
    • 若优先级大于栈顶，则直接入栈；
    • 若优先级小于等于栈顶，弹出栈顶并输出，然后不断与新的栈顶比较，直至优先级大于栈顶或栈空或栈顶为左括号'('，再将该运算符入栈；
• 表达式遍历完毕，弹出符号栈内剩余所有运算符并输出，结果字符串即为后缀表达式。

1.3.2 后缀表达式计算机求值

从左至右扫描后缀表达式，遇到数字直接入栈，遇到运算符弹出栈中两个元素，用运算符对其进行相应运算，并将结果再次入栈。重复上述步骤直至遍历完表达式，最终运算完的结果即为表达式的结果。eg.上述例子1+((2+3)×4)-5对应的后缀表达式为：123+4×+5-，针对该表达式求值步骤为：

• 从左至右扫描，将1，2，3压入栈中；
• 遇到'+'，弹出2，3计算2+3，将结果5再次压入栈中；
• 4入栈；
• 遇到'×'，弹出4，5计算4×5，将结果20压入栈中；
• 遇到'+'，弹出20，1计算20+1，将结果21压入栈中；
• 5入栈；
• 遇到'-'，弹出5，21计算21-5，结果16即为表达式的值。

2. 逆波兰表达式计算器

2.1 思路分析

（1）输入一个逆波兰表达式（后缀表达式），运用栈Stack计算其结果；

（2）支持小括号和多位整数；

（3）将原本存储表达式的字符串suffixExpression放到ArrayList中，通过遍历ArrayList配合原生栈Stack完成计算。这样做的好处是不需要原来的index扫描字符串，直接遍历ArrayList更快更便捷；

（4）匹配多位数字时可以直接用正则表达式"\d+"。

2.2 代码实现

package com.datastructure;

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

/**
 * @author SnkrGao
 * @create 2023-03-30 14:54
 */
public class ReversePolishNotationCalculator {

    public static void main(String[] args) {

        // 先给定一个逆波兰表达式1 + ( ( 2 + 3 ) * 4 ) - 5 => 1 2 3 + 4 * + 5 -
        //                    4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / +
        // 为了方便后续ArrayList处理以及支持多位整数，将表达式的数字、运算符之间都用空格隔开
//        String suffixExpression = "1 2 3 + 4 * + 5 -";
        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";

        ArrayList<String> rpnList = getList(suffixExpression);
        System.out.println("rpnList=" + rpnList);

        int result = calculate(rpnList);
        System.out.println("计算结果为：" + result);
    }

    // 将suffixExpression后缀表达式放入ArrayList
    public static ArrayList<String> getList(String suffixExpression) {
        // 用空格分割表达式，并将数字与运算符存入字符串数组
        String[] split = suffixExpression.split(" ");
        ArrayList<String> list = new ArrayList<>();
        for (String item : split) {
            list.add(item);
        }
        return list;
    }

    public static int calculate(ArrayList<String> list) {
        // 创建一个栈，用于辅助计算
        Stack<String> stack = new Stack<>();
        for (String item : list) {
            // 正则表达式匹配多位数字
            if (item.matches("\\d+")) {
                stack.push(item);
            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num2 - num1;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num2 / num1;
                } else {
                    throw new RuntimeException("表达式符号有误！");
                }
                // res为int类型需转为String后入栈
                stack.push("" + res);
            }
        }
        // 返回计算结果，即最终留在栈中的数
        return Integer.parseInt(stack.pop());
    }
}

3. 中缀表达式转后缀表达式代码实现

package com.datastructure;

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

/**
 * @author SnkrGao
 * @create 2023-03-30 20:56
 */
public class InfixToSuffix {

    public static void main(String[] args) {

        // 给定一个中缀表达式，不同于后缀表达式，由于有()因此不用空格分隔
        String infixExpression = "1+((2+3)*4)-5";
        // 将中缀表达式转为对应的list => [1,+,(,(,2,+,3,),*,4,),-,5]
        ArrayList<String> infixList = getInfixExpressionList(infixExpression);
        System.out.println("中缀表达式对应的list="+infixList);

        // 将infixList转为后缀表达式对应的list => [1, 2, 3, +, 4, *, +, 5, -]
        ArrayList<String> suffixList = transferSuffixExpressionList(infixList);
        System.out.println("后缀表达式对应的list="+suffixList);

        // 计算后缀表达式结果
        System.out.println("该中缀表达式转后缀表达式后的计算结果为："+calculate(suffixList));
    }

    public static int calculate(ArrayList<String> list) {
        Stack<String> stack = new Stack<>();

        for (String item : list) {
            if (item.matches("\\d+")) {
                stack.push(item);
            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;

                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num2 - num1;
                } else if (item.equals("*")) {
                    res = num2 * num1;
                } else if (item.equals("/")) {
                    res = num2 / num1;
                } else {
                    throw new RuntimeException("符号有误！");
                }
                stack.push("" + res);
            }
        }
        return Integer.parseInt(stack.pop());
    }

    public static ArrayList<String> getInfixExpressionList(String expression) {
        ArrayList<String> list = new ArrayList<>();

        int index = 0; // 用于遍历
        char c; // 用于存储每次遍历的字符
        String str = ""; // 用于拼接多位数字

        do {
            // 不是数字，直接添加进list
            if ((c = expression.charAt(index)) > '9' || (c = expression.charAt(index)) < '0') {
                list.add("" + c);
                index++;
            } else { // 若是数字，考虑多位数
                while (index < expression.length() && (c = expression.charAt(index)) <= '9' && (c = expression.charAt(index)) >= '0') {
                    str += c;
                    index++;
                }
                list.add(str);
                str = ""; // 清空str用于下一次拼接多位数
            }
        } while (index < expression.length());
        return list;
    }

    public static ArrayList<String> transferSuffixExpressionList(ArrayList<String> list) {
        Stack<String> s1 = new Stack<>(); // 符号栈
        ArrayList<String> s2 = new ArrayList<>(); // 结果list

        for (String item : list) {
            // 正则表达式判断是否为数以及多位数，若是则add进s2
            if (item.matches("\\d+")) {
                s2.add(item);
            } else if (item.equals("(")) { // 左括号直接进符号栈
                s1.push(item);
            } else if (item.equals(")")) { // 右括号需循环判断栈顶，只要不是左括号，就出栈并添加到s2
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop(); // 把"("和")"消掉
            } else {
                // 若为运算符，则判断其与s1栈顶符号的优先级
                while (!s1.isEmpty() && !s1.peek().equals("(") && Operation.getPriority(item) <= Operation.getPriority(s1.peek())) {
                    s2.add(s1.pop());
                }
                s1.push(item);
            }
        }

        // 将s1中剩余符号都add进s2中
        while (!s1.isEmpty()) {
            s2.add(s1.pop());
        }
        // 将s2顺序输出即是后缀表达式对应的list
        return s2;
    }
}

// 返回给定操作符对应的优先级
class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    public static int getPriority(String operation) {
        int res = 0;
        switch (operation) {
            case "+":
                res = ADD;
                break;
            case "-":
                res = SUB;
                break;
            case "*":
                res = MUL;
                break;
            case "/":
                res = DIV;
                break;
            default:
                break;
        }
        return res;
    }
}