中缀表达式转后缀表达式

一、前置知识

在学习中缀表达式转后缀表达式之前，需要先掌握以下几个概念。

1、中缀表达式：指运算符在中间位置的表达式，例如1+2。

2、前缀表达式：指运算符在前面位置的表达式，例如+12。

3、后缀表达式：指运算符在后面位置的表达式，例如12+。

4、运算符优先级：指不同运算符之间的优先级大小，例如乘法的优先级高于加法。

二、中缀表达式转后缀表达式的基本流程

1、从左到右扫描中缀表达式中的每一个数字或者运算符。

2、如果是数字，直接输出到后缀表达式中。

3、如果是左括号，进栈。

4、如果是右括号，将左括号上面的运算符全部弹出栈并输出到后缀表达式中，左右括号不输出。

5、如果是运算符，如果它的优先级比栈顶的运算符高，将它压入栈中。否则，将栈顶的运算符弹出，并输出到后缀表达式中，直到该运算符的优先级大于栈顶运算符的优先级为止。

6、重复步骤1~5，直到中缀表达式扫描完毕。

7、将栈内剩余的运算符依次弹出并输出到后缀表达式中。

三、代码实现

import java.util.Stack;
public class InfixToPostfix {
    public static void main(String[] args) {
        String infixExp = "(1+2)*3-4/5";
        String postfixExp = infixToPostfix(infixExp);
        System.out.println(postfixExp);
    }
    public static String infixToPostfix(String infixExp) {
        Stack operatorStack = new Stack();
        StringBuilder postfixExp = new StringBuilder();
        for (char ch : infixExp.toCharArray()) {
            if (ch >= '0' && ch <= '9') { // 判断数字
                postfixExp.append(ch);
            } else if (ch == '(') { // 左括号直接进栈
                operatorStack.push(ch);
            } else if (ch == ')') { // 右括号弹出栈内全部运算符
                while (operatorStack.peek() != '(') {
                    postfixExp.append(operatorStack.pop());
                }
                operatorStack.pop(); // 弹出左括号
            } else { // 运算符
                while (!operatorStack.isEmpty() && operatorStack.peek() != '(' && priority(ch) <= priority(operatorStack.peek())) {
                    postfixExp.append(operatorStack.pop());
                }
                operatorStack.push(ch);
            }
        }
        while (!operatorStack.isEmpty()) { // 栈内剩余的运算符全部输出
            postfixExp.append(operatorStack.pop());
        }
        return postfixExp.toString();
    }
    private static int priority(char ch) { // 运算符优先级，数字越大，优先级越高
        if (ch == '+' || ch == '-') {
            return 1;
        } else if (ch == '*' || ch == '/') {
            return 2;
        } else {
            return 0; // 括号优先级最高
        }
    }
}

四、实例演示

例如，将中缀表达式“(1+2)*3-4/5”转换为后缀表达式如下：

1 2 + 3 * 4 5 / –

代码运行结果如下：

1+2 -> 12+
(1+2)*3 -> 12+3*
4/5 -> 45/
(1+2)*3-4/5 -> 12+3*45/- -> 12+3*4/5-

五、总结

中缀表达式转后缀表达式使用了栈的思想，通过将运算符依次压入和弹出栈来实现转换功能。在代码实现时，需要注意运算符优先级的大小以及左右括号的处理方式。

掌握了中缀表达式转后缀表达式的知识后，可以在实际编程中更加轻松地操作表达式的计算。