前缀、中缀、后缀表达式

前缀表达式是一种没有括号的算术表达式，与中缀表达式不同的是，其将运算符写在前面，操作数写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz，前缀表达式也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)。（从左至右）

中缀表达式是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（例：3 + 4），中缀表达式是人们常用的算术表示方法。
与前缀表达式（例：+ 3 4）或后缀表达式（例：3 4 +）相比，中缀表达式不容易被计算机解析，但仍被许多程序语言使用，因为它符合人们的普遍用法。
与前缀或后缀记法不同的是，中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。

逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后），例如（3+4）×5-6的逆波兰表达式是3 4 + 5 × 6 -。(从右至左)

完成一个简易的逆波兰计算器，要求完成以下任务：

• 输入一个逆波兰表达式（后缀表达式），使用栈计算其结果
• 支持小括号和多位数整数

实现思路：

• 例如(3+4)×5-6所对应的后缀表达式为3 4 + 5 × 6 -，从左至右开始扫描表达式，若遇到运算符，则将栈顶元素和次顶元素弹出，并计算值，将计算结果入栈
• 例如，当我们从左到右扫描时，将3和4入栈，直到扫描到+号时，将栈顶元素3和次顶元素4出栈，并将3+4=7的结果入栈（当运算符为减号或者是除号时，计算的顺序不能搞错）

public class PolandNotation {
    public static void main(String[] args) {
        // 为了说明方便，逆波兰表达式的数字和符号都使用空格隔开
        String str = "3 4 + 5 * 6 -";
        List<String> list = getListString(str);
        int i = caculate(list);
        System.out.println(i);

    }
    public static List<String> getListString(String expression) {
        // split() 方法根据匹配给定的正则表达式来拆分字符串
        String[] split = expression.split(" ");
        List<String> list = new ArrayList<>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }
    public static int caculate(List<String> list) {
        LinkedStack stack = new LinkedStack();
        for(String ele : list) {
            // 这里使用正则表达式来取出数
            if (ele.matches("\\d+")) { // 匹配的是一个多位数
                stack.push(ele);
            } else {
                int num1 = Integer.parseInt(stack.pop().toString());
                int num2 = Integer.parseInt(stack.pop().toString());
                int result = 0;
                if(ele.equals("+")) {
                    result = num1 + num2;
                } else if (ele.equals("-")) {
                    result = num2 - num1;
                } else if (ele.equals("*")) {
                    result = num1 * num2;
                } else if (ele.equals("/")) {
                    result = num2 / num1;
                } else {
                    try {
                        throw new Exception("表达式有误！");
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                }
                stack.push(result);
            }
        }
        return Integer.parseInt(stack.pop().toString());
    }
}

但现在问题来了，后缀表达式确实适合用来计算，但是人为写的话确实有些麻烦，尤其是在表达式很长的情况下，因此我们需要一个方案，将中缀表达式转为后缀表达式！

具体实现思路和表达式求值分析非常相似，下面进行分析：

1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2
2. 从左到右扫描表达式
3. 遇到操作数时，将其压入s2
4. 遇到运算符时，比较当前运算符和s1栈顶运算符的优先级
   1. 如果s1为空，或者是s1的栈顶运算符为左括号"("则直接将运算符入栈
   2. 如果s1不为空，且当前运算符的优先级比栈顶运算符优先级高，则将当前运算符入栈
   3. 如果当前运算符的优先级低于或等栈顶运算符，将栈顶运算符出栈并压入到s2中，然后再回到第1步继续和下一个栈顶运算符进行优先级比较
5. 遇到括号时：
   1. 如果是左括号“(”，则直接压入s1中
   2. 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入到s2，直到遇到左括号为止，然后将这一对括号丢弃
6. 重复步骤2至5，直到表达式扫描完为止
7. 将s1中剩余的运算符依次弹出并压入s2中
8. 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

需要注意的是：在以上步骤分析中，栈s2并没有进行出栈操作，而且最后的结果需要栈的逆序输出，比较麻烦，所以我们可以使用链表来替换s2的栈！

假设，当前需要转换成后缀表达式的中缀表达式为：1+((2+3)*4)-5，为了方便后续的操作，我们可以先将表达式字符串依次加入链表中。

当表达式加入至链表后，输出应该为[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]。

// 将中缀表达式中的字符添加进ArrayList链表中
public static List<String> toInfixExpression(String s) {
    List<String> list = new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
        char cc = s.charAt(i);
        // 使用isDigit方法判断字符是否为数字
        if (Character.isDigit(cc)) {
            StringBuilder sb = new StringBuilder();
            // 若数字不止一位数时
            while(Character.isDigit(cc)) {
                sb.append(cc);
                i++;
                if (i >= s.length()) {
                    break;
                }
                cc = s.charAt(i);
            }
            list.add(sb.toString());
            i--;
        } else {
            StringBuilder sb = new StringBuilder();
            sb.append(cc);
            list.add(sb.toString());
        }
    }
    return list;
}

再将中缀表达式转换为后缀表达式之前，上述步骤所描述的操作有一个为“比较优先级”的操作，于是我们需要先创建一个方法，来比较优先级，我们规定“+”、“-”为第二优先级，“*”、“/”为第一优先级，分别返回不同的数字！

// 定义一个比较优先级的方法
public static int operation(String operation) {
    int result = 0;
    switch (operation) {
        case "+":
            result = 1;
            break;
        case "-":
            result = 1;
            break;
        case "*":
            result = 2;
            break;
        case "/":
            result = 2;
            break;
        default:
            try {
                throw new Exception("优先级比较有误！");
            } catch (Exception e) {
                e.printStackTrace();
            }
    }
    return result;
}

按照上述分析步骤，实现中缀表达式转后缀表达式：

// 将中缀表达式转换为后缀表达式
public static List<String> parseSuffixExpression(List<String> list) {
    Stack<String> s1 = new Stack();
    // 使用链表替换栈
    List<String> s2 = new ArrayList<>();
    for (String item : list) {
        // 使用正则表达式来判断是否为数字
        if (item.matches("\\d+")) {
            s2.add(item);
        } else if(s1.isEmpty() || s1.peek().equals("(")) {
            // 当s1为空且s1栈顶运算符为"("时
            s1.push(item);
        } else if (item.equals("(")) {
            // 当前运算符为"("时
            s1.push(item);
        } else if(item.equals(")")) {
            // 当前运算符为")"，将s1栈顶元素出栈，直到栈顶元素为")"时
            while ( ! s1.peek().equals("(")) {
                s2.add(s1.pop());
            }
            // 丢弃一对括号
            s1.pop();
        } else {
            while( ! s1.isEmpty() && operation(s1.peek()) >= operation(item)) {
                s2.add(s1.pop());
            }
            s1.push(item);
        }
    }
    // 将s1中剩余的运算符加入s2中
    while( ! s1.isEmpty()) {
        s2.add(s1.pop());
    }
    return s2;
}

结合上述几个代码实例，我们就可以写出关于中缀表达式的简易计算器，不过，需要注意的是，输入的中缀表达式如果有空格，那需要把空格剔除，可以使用正则表达式，也可以使用Character类的isWhitespace()方法！