算术表达式之前缀、中缀、后缀表达式转化

概述

前缀、中缀、后缀表达式一般是根据操作符的位置来确定的，在我们去理解什么是前缀表达式和后缀表达式之前，可以先看下中缀表达式是什么？看如下的例子:
(3+4)* 5— 6 这就是我们正常一般看到的表达式。

虽然中缀表达式符合我们人的日常思维习惯，但是计算机在存储中缀表达式时，需要使用树这种数据结构(思考下，这里是因为包括括号的概念)，如果表达式过于复杂，那么树的高度会变得很高，大大增加了时间复杂度和空间复杂度。如果转换成线性结构，那么效率将变得高很多，所以需要将中缀表达式先转换成前缀或者后缀表达式，然后依靠栈这种线性数据结构来进行计算。一般计算机中存储基本是转成后缀表达式，然后来进行求值。

前缀表达式

前缀表达式又称为波兰表达式，他的特点是运算符位于操作数之前。
举例说明，(3+4) x 5 - 6 转为前缀表达式就是 - X + 3 4 5 6 .

中缀表达式如何转化成前缀表达式

      *(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
     * (2) 从右至左扫描中缀表达式；
     * (3) 遇到操作数时，将其压入S2；
     * (4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
     * (4-1) 如果S1为空，则直接将此运算符入栈；
     * (4-2) 否则，若优先级比栈顶运算符的较高或相等(后缀表达式中是较高,没有相等)或栈顶运算符为右括号“)”，
        也将运算符压入S1；
     * (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
     * (5) 遇到括号时：
     * (5-1) 如果是右括号“)”，则直接压入S1；
     * (5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃
     * (6) 重复步骤(2)至(5)，直到表达式的最左边；
     * (7) 将S1中剩余的运算符依次弹出并压入S2；
     * (8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
     * (后缀表达式这里要将字符串反转输出,这里直接输出即可)

下面是进行转化的步骤:

这个是代码实现:

private static String zhong2Qian(String expression) {

        //(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2;
        Stack<Character> ops = new Stack<>();
        Stack<Character> resultValues = new Stack<>();

        //(2) 从右至左扫描中缀表达式;这里是先反转字符串再遍历其字符数组
        expression = reverseString(expression);
        char[] chars = expression.toCharArray();
        for (char theChar : chars) {
            //(3) 遇到操作数时，将其压入S2;
            if (Character.isDigit(theChar))
                resultValues.push(theChar);
            //(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
            else if (theChar == '+' || theChar == '-' || theChar == '*' || theChar == '/') {
                    dealTheChar(ops, resultValues, theChar);

            }
            //(5-1) 如果是右括号“)”，则直接压入S1；
            else if (theChar == ')')
                ops.push(theChar);
            //(5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃;
            else if (theChar == '(') {
                char opsChar = ops.pop();
                while (opsChar != (')')) {
                    resultValues.push(opsChar);
                    opsChar = ops.pop();
                }
            }
        }

        //(7)将S1中剩余的运算符依次弹出并压入S2；
        while (!ops.empty()) {
            resultValues.push(ops.pop());
        }

        //(8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
        // (后缀表达式这里要将字符串反转输出,这里直接输出即可)
        StringBuilder exp = new StringBuilder();
        while (!resultValues.empty())
            exp.append(resultValues.pop());

        return exp.toString();
    }

后缀表达式

后缀表达式又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作符之后，转化时时从左边往右扫描表达式的。这也是计算机中主要的存储算术表达式的方式。

中缀表达式如何转化成前缀表达式

/**
     * 将中缀表达式转换为后缀表达式：
     与转换为前缀表达式相似，遵循以下步骤：
     * (1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
     * (2) 从左至右扫描中缀表达式；
     * (3) 遇到操作数时，将其压入S2；
     * (4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
     * (4-1) 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
     * (4-2) 否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，
            而这里则不包括相同的情况）；
     * (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
     * (5) 遇到括号时：
     * (5-1) 如果是左括号“(”，则直接压入S1；
     * (5-2) 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
     * (6) 重复步骤(2)至(5)，直到表达式的最右边；
     * (7) 将S1中剩余的运算符依次弹出并压入S2；
     * (8) 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。
     * @return
     */

计算会比较复杂，所以这里用两个例子:

(1): 中缀表达式 1+((2 + 3) x 4)-5

结果为: 1 2 3 + 4 x + 5 -

(2): 中缀表达式 ( 3+ 4) x 5 -6

代码实现如下:

 private static String zhong2hou(String expression) {

        //(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
        Stack<Character> ops = new Stack<>();
        Stack<Character> resultValues = new Stack<>();

        char[] chars = expression.toCharArray();

        //(2) 从左至右扫描中缀表达式；
        for (char theChar : chars){
            //(3) 遇到操作数时，将其压入S2；
            if (Character.isDigit(theChar))
                resultValues.push(theChar);
            //(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
            else if (theChar == '+' || theChar == '-' || theChar == '*' || theChar == '/')
                dealTheChar(ops,resultValues,theChar);
            //(5) 遇到括号时：
            //(5-1) 如果是左括号“(”，则直接压入S1；
            else if (theChar == '(')
                ops.push(theChar);
            //(5-2) 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
            else if (theChar == ')'){
                char opsChar  = ops.pop();
                while (opsChar != '(') {
                    resultValues.push(opsChar);
                    opsChar  = ops.pop();
                }
            }
        }

        //(7) 将S1中剩余的运算符依次弹出并压入S2；
        while (!ops.isEmpty())
            resultValues.push(ops.pop());
        
        //(8) 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。
        StringBuilder exp = new StringBuilder();
        while (!resultValues.empty())
            exp.append(resultValues.pop());

        return reverseString(exp.toString());
    }

private static void dealTheChar(Stack<Character> ops, Stack<Character> resultValues, char theChar) {
        //(4-1) 如果S1为空，则直接将此运算符入栈;
        if (ops.empty()) {
            ops.push(theChar);
            return;
        }
        char popTheChar = ops.pop().charValue();
        //(4-1) 如果S1为空，或栈顶运算符为右括号“(”，则直接将此运算符入栈;
        //(4-2) 否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）
        if (popTheChar == '(' || getPriorityValue(theChar) > getPriorityValue(popTheChar)) {
            ops.push(popTheChar);
            ops.push(theChar);
        }
        //(4-3) 否则，将S1栈顶的运算符弹出并压入到S2中
        else {
            resultValues.push(popTheChar);
            //，再次转到(4-1)与S1中新的栈顶运算符相比较;
            dealTheChar(ops, resultValues, theChar);
        }
    }