Java编程实现逆波兰表达式代码示例

让我来为您详细讲解Java编程实现逆波兰表达式代码示例的攻略。

什么是逆波兰表达式？

逆波兰表达式（Reverse Polish Notation，RPN）是一种无括号的计算表达式，其中操作符在操作数后面。例如，中缀表达式 3 + 4 * 5 可以转换为逆波兰表达式 3 4 5 * +。

实现逆波兰表达式求值

步骤一：将中缀表达式转换为逆波兰表达式

我们可以使用栈来实现中缀表达式的转换。具体步骤如下：

1. 初始化一个栈和一个字符串列表。
2. 从左到右遍历中缀表达式，如果遇到操作数，则将其直接加入到字符串列表中。
3. 如果遇到左括号，则将其压入栈中。
4. 如果遇到右括号，则弹出栈中的所有操作符，将这些操作符加入到字符串列表中，直到遇到左括号。
5. 如果遇到操作符，则将其弹出栈中，与栈顶元素比较优先级。
6. 如果栈顶元素优先级高于或等于当前操作符，则将栈顶元素加入到字符串列表中，重复此步骤，直到栈顶元素优先级低于当前操作符，然后将当前操作符压入栈中。
7. 如果栈顶元素优先级低于当前操作符，则将当前操作符压入栈中。
8. 遍历完中缀表达式后，将栈中所有操作符依次弹出并加入到字符串列表中。

以下是示例代码：

import java.util.*;

public class InfixToPostfix {
    private static final Map<String, Integer> precedence = new HashMap<>() {{
        put("+", 1);
        put("-", 1);
        put("*", 2);
        put("/", 2);
    }};

    public static List<String> infixToPostfix(String infix) {
        Stack<String> stack = new Stack<>();
        List<String> postfix = new ArrayList<>();

        for (String token : infix.split("\\s")) {
            switch (token) {
                case "(":
                    stack.push(token);
                    break;
                case ")":
                    while (!stack.peek().equals("(")) {
                        postfix.add(stack.pop());
                    }
                    stack.pop();
                    break;
                case "+":
                case "-":
                case "*":
                case "/":
                    while (!stack.isEmpty() && !stack.peek().equals("(") && precedence.get(stack.peek()) >= precedence.get(token)) {
                        postfix.add(stack.pop());
                    }
                    stack.push(token);
                    break;
                default:
                    postfix.add(token);
                    break;
            }
        }

        while (!stack.isEmpty()) {
            postfix.add(stack.pop());
        }

        return postfix;
    }
}

例如，将 3 + 4 * 5 转换为逆波兰表达式，可以调用以下代码：

InfixToPostfix.infixToPostfix("3 + 4 * 5");

输出结果为 [3, 4, 5, *, +]。

步骤二：使用逆波兰表达式求值

我们可以使用栈来实现逆波兰表达式的求值。具体步骤如下：

1. 初始化一个操作数栈。
2. 从左到右遍历逆波兰表达式，如果遇到操作数，则将其压入操作数栈中。
3. 如果遇到操作符，则弹出操作数栈中的两个操作数，将这两个操作数进行计算，并将计算结果压入操作数栈中。
4. 遍历完逆波兰表达式后，操作数栈中的唯一元素即为表达式的最终值。

以下是示例代码：

import java.util.*;

public class EvaluatePostfix {
    public static int evaluatePostfix(List<String> postfix) {
        Stack<Integer> stack = new Stack<>();

        for (String token : postfix) {
            switch (token) {
                case "+":
                    int b = stack.pop();
                    int a = stack.pop();
                    stack.push(a + b);
                    break;
                case "-":
                    b = stack.pop();
                    a = stack.pop();
                    stack.push(a - b);
                    break;
                case "*":
                    b = stack.pop();
                    a = stack.pop();
                    stack.push(a * b);
                    break;
                case "/":
                    b = stack.pop();
                    a = stack.pop();
                    stack.push(a / b);
                    break;
                default:
                    stack.push(Integer.parseInt(token));
                    break;
            }
        }

        return stack.pop();
    }
}

例如，对逆波兰表达式 [3, 4, 5, *, +] 求值，可以调用以下代码：

EvaluatePostfix.evaluatePostfix(Arrays.asList("3", "4", "5", "*", "+"));

输出结果为 23。

结语

以上就是Java编程实现逆波兰表达式代码示例的攻略，希望能对您有所帮助。