Java实现中缀表达式转后缀表达式（附代码示例）

Java实现中缀表达式转后缀表达式

在计算机科学中，中缀表达式是我们日常生活中常用的数学表达式形式，例如 (2+5)*3-5*7。然而，对于计算机来说，后缀表达式更易于解析和计算。

本文将介绍如何使用Java将中缀表达式转换为后缀表达式，并提供完整的代码示例和算法解释。

算法原理

中缀表达式转后缀表达式的主要思路是利用栈来存储操作符，并根据操作符的优先级进行处理。算法步骤如下：

从左到右扫描中缀表达式。
如果遇到操作数，直接输出到后缀表达式。
如果遇到操作符：
- 如果栈为空，或栈顶元素为左括号，则将该操作符入栈。
- 否则，比较该操作符与栈顶操作符的优先级：
  - 如果该操作符优先级高于栈顶操作符，则将该操作符入栈。
  - 如果该操作符优先级低于或等于栈顶操作符，则将栈顶操作符弹出并输出到后缀表达式，然后重复步骤3。
如果遇到左括号，将其入栈。
如果遇到右括号，则将栈中元素依次弹出并输出到后缀表达式，直到遇到左括号为止（左括号也弹出但不输出）。
扫描完中缀表达式后，将栈中剩余的操作符依次弹出并输出到后缀表达式。

Java代码示例

import java.util.Stack;

public class InfixToPostfix {
    // 检查操作符的优先级
    private static int precedence(char ch) {
        switch (ch) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            case '^':
                return 3;
        }
        return -1;
    }

    // 将中缀表达式转换为后缀表达式
    public static String infixToPostfix(String infix) {
        StringBuilder postfix = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < infix.length(); i++) {
            char ch = infix.charAt(i);

            // 如果是操作数，直接添加到后缀表达式
            if (Character.isLetterOrDigit(ch)) {
                postfix.append(ch);
            }
            // 如果是左括号，入栈
            else if (ch == '(') {
                stack.push(ch);
            }
            // 如果是右括号，将栈内的操作符弹出直到遇到左括号
            else if (ch == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    postfix.append(stack.pop());
                }
                stack.pop(); // 弹出左括号
            }
            // 如果是操作符
            else {
                while (!stack.isEmpty() && precedence(ch) <= precedence(stack.peek())) {
                    postfix.append(stack.pop());
                }
                stack.push(ch);
            }
        }

        // 将栈内剩余的操作符添加到后缀表达式
        while (!stack.isEmpty()) {
            if (stack.peek() == '(') {
                return "Invalid infix expression";
            }
            postfix.append(stack.pop());
        }

        return postfix.toString();
    }

    public static void main(String[] args) {
        String infixExpression = "(2+5)*3-5*7";
        String postfixExpression = infixToPostfix(infixExpression);
        System.out.println("中缀表达式: " + infixExpression);
        System.out.println("后缀表达式: " + postfixExpression);
    }
}

示例输出

中缀表达式: (2+5)*3-5*7
后缀表达式: 25+3*57*-

这段代码将中缀表达式 (2+5)*3-5*7 转换为后缀表达式 25+3*57*-。

总结

本文介绍了如何使用Java将中缀表达式转换为后缀表达式，并提供了完整的代码示例和算法解释。理解该算法对于学习数据结构和算法基础知识非常有帮助，也为后续学习编译原理打下基础。